排列与寻找递归较少的相同字符串

Question

我目前在解决课程中的一个编程问题时遇到了一些困难。

问题如下:

给定k个不同的小写英文字符串，如果第i个和第j个字符串的连接产生一个新的字符串X，该字符串可以分成两个相同的子字符串{X, X}，请返回i和j的所有可能的组合。

约束条件为k<80000，每个字符串的长度为<200。

我写了一个可以正常工作的程序，但是它的时间复杂度是O(k*(k-1)/2)。我现在正试图将其时间复杂度降低到O(k*string_length)，但我不确定如何实现这一点。

这是我当前的代码:

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

Answer 1

将字符串作为键放在哈希表中，并将其索引作为值。

看每个字符串a，它有多少种写法是x+y+x?查看x的所有可能长度，并查看第一个字符是否与最后一个字符相同。如果y恰好是哈希表中的一个键，则a和y是一对。

这是家庭作业。你应该自己写代码。