CODEWITHSUNDEEP
pythonstringrecursionpermutation
Jaro Cho
Jaro Cho

Reputation: 1

Permutations and Finding the Same String with Fewer Recursion

I am currently facing some difficulties with solving a programming problem in my course.

The problem is as follows:

given k distinct lowercase English strings, if the concatenation of the i-th and j-th string yields a new string X that can be split into two identical substrings {x,x}, please return all possible combinations of i and j.

The constraints are that k<80000 and the length of each string is <200.

I have written a program that works correctly, but its time complexity is O(k*(k-1)/2). I am now trying to reduce its time complexity to O(k*string_length), but I am not sure how to achieve this.

this is my current code:

def pair2(strSet, k):
    ans = 0
    ans_set = set()
    runtime = 0
    for i in range(k):
        ele1 = strSet[i]
        for j in range(i + 1, k):
            ele2 = strSet[j]
            runtime += 1
            new_ele = ele1 + ele2
            if len(new_ele) % 2 == 0:
                half = len(new_ele) // 2
                left_ele = new_ele[:half]
                right_ele = new_ele[half:]
                if left_ele == right_ele and (ele1, ele2) not in ans_set and (ele2, ele1) not in ans_set:
                    ans += 1
                    ans_set.add((ele1, ele2))
    #print(runtime)
    return ans

k = 5 
strSet = ['aca', 'baab', 'c', 'aa', 'bacab']
print(pair2(strSet, k))
#output is 3

k = 7 
strSet = ['aaaa', 'a', 'aaa', 'c', 'bbcbb', 'kkk', 'abcdcd']
print(pair2(strSet, k))
#output is 2

Upvotes: 0

Views: 49

Answers (1)

Frank Yellin
Frank Yellin

Reputation: 11285

Put the strings as keys in a hash table, with their indices as the value.

Look at each string a. How many ways can it be written as x+y+x? Look at every possible length of x and see if the first characters are the same as the final characters. If y happens to be a key in the hash table, then a and y are a pair.

This is homework. You should write the code yourself.

Upvotes: 0

Related Questions