问题如下：如果有两个字符串str1和str2，以及另一个字符串str3，则编写一个函数来检查str3是否同时包含原始序列中的str1和str2字母，尽管它们可能是交错的。因此，对于子字符串adf和bec，adbfec返回true。我用python编写了以下函数：
def isinter(str1,str2,str3):
p1,p2,p3 = 0,0,0
while p3 < len(str3):
if p1 < len(str1) and str3[p3] == str1[p1]:
p1 += 1
elif p2 < len(str2) and str3[p3] == str2[p2]:
p2 += 1
else:
break
p3 = p1+p2
return p3 == len(str3)
这个程序还有另一个版本，位于ardentart（最后一个解决方案）现在哪个更好？我想是我的，因为它可能是线性的。不管是不是更好，我的算法还有进一步的优化空间吗？
最佳答案
您可以在列表中拆分所有三个字符串：
list1 = list(str1)
然后用现在使用的相同算法遍历
list3，检查list3[i]是否等于list1[0]或list2[0]如果是的话，你会从适当的列表中选择。过早的列表结束可能会被捕获为异常。
算法将完全相同，但实现应该更高效。
更新：事实上不是（大约是时间的两倍）哦，好吧，也许知道会有用。
在对不同场景进行基准测试时，发现除非指定三个字符串长度是“精确的”（即len（p1）+len（p2）==len（p3）），否则最有效的优化方法是首先检查这将立即丢弃两个输入字符串由于字符串长度错误而无法匹配第三个字符串的所有情况。
然后我遇到了两个字符串中都有同一个字母的情况，将它赋给list1或list2可能会导致其中一个字符串不再匹配。在这些情况下，算法失败，出现假阴性，这将需要递归。
def isinter(str1,str2,str3,check=True):
# print "Checking %s %s and %s" % (str1, str2, str3)
p1,p2,p3 = 0,0,0
if check:
if len(str1)+len(str2) != len(str3):
return False
while p3 < len(str3):
if p1 < len(str1) and str3[p3] == str1[p1]:
if p2 < len(str2) and str3[p3] == str2[p2]:
# does str3[p3] belong to str1 or str2?
if True == isinter(str1[p1+1:], str2[p2:], str3[p3+1:], False):
return True
if True == isinter(str1[p1:], str2[p2+1:], str3[p3+1:], False):
return True
return False
p1 += 1
elif p2 < len(str2) and str3[p3] == str2[p2]:
p2 += 1
else:
return False
p3 += 1
return p1 == len(str1) and p2 == len(str2) and p3 == len(str3)
然后我在随机字符串上运行了一些基准测试，这就是工具（注意，它总是生成有效的shuffles，这可能会产生有偏差的结果）：
for j in range(3, 50):
str1 = ''
str2 = ''
for k in range(1, j):
if random.choice([True, False]):
str1 += chr(random.randint(97, 122))
if random.choice([True, False]):
str2 += chr(random.randint(97, 122))
p1 = 0
p2 = 0
str3 = ''
while len(str3) < len(str1)+len(str2):
if p1 < len(str1) and random.choice([True, False]):
str3 += str1[p1]
p1 += 1
if p2 < len(str2) and random.choice([True, False]):
str3 += str2[p2]
p2 += 1
a = time.time()
for i in range(1000000):
isShuffle2(str1, str2, str3)
a = (time.time() - a)
b = time.time()
for i in range(1000000):
isinter(str1, str2, str3)
b = (time.time() - b)
print "(%s,%s = %s) in %f against %f us" % (str1, str2, str3, a, b)
结果似乎表明，对于短字符串，cached+DP算法的效率更高当字符串变长（超过3-4个字符）时，cache+dp算法开始失去优势。在长度约为10的情况下，上述算法的执行速度是完全递归的缓存版本的两倍。
如果字符串包含重复字符（我是通过限制从a-z到a-i的范围来实现的）并且重叠很小，dp算法的性能会更好，但仍然比上面的算法差。例如，在这种情况下，DP仅损失2us：
(cfccha,ddehhg = cfcchaddehhg) in 68.139601 against 66.826320 us
毫不奇怪，完全重叠（每个字符串依次有一个字母）会看到更大的差异，比率高达364:178（略高于2:1）。