1

问题如下：如果有两个字符串str1和str2，以及另一个字符串str3，编写一个函数来检查是否str3包含str1' 字母 和str2' 字母，它们的序列是否与原始序列相同，尽管它们可能是交错的。因此，adbfec为子字符串adf和bec返回 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（最后一个解决方案）。现在哪个更好？我认为是我的，因为它可能在线性时间内完成。不管好不好，我的算法还有进一步优化的空间吗？

4

4 回答 4

2

不幸的是，您的版本无法正常工作。想象一下输入 ab, ac, acab. 您的算法返回False不正确。

str1问题是当看到的字母str3可以双向解释时，你总是走路；str2可能需要走路，但它不会与您的算法获得平等的机会。

于 2012-09-23T22:40:00.753 回答
1

另一种方法是使用python的正则表达式模块re。您可以拆分 str1 的字符，并用 .* 包围每个字符以匹配它们之间的任意数量（或无）字符。这将为您提供匹配 str1 的模式。然后对 str2 执行相同的操作，然后只需运行 re.match(str1pattern, str3) 和 re.match(str2pattern, str3)。如果它们都返回对象（即除了 None 之外的任何东西），那么你对这两个字符串都有一个匹配项。

这可能会更好地扩展，因为它更容易添加更多要检查的字符串，如果您需要更好的性能来搜索各种其他字符串，那么您也可以编译模式。

于 2012-09-23T22:24:33.637 回答
1

您可以拆分列表中的所有三个字符串：

list1 = list(str1)

然后list3用你现在使用的相同算法行走，检查是否list3[i]等于list1[0]或list2[0]。如果是的话，您会del从相应的列表中获得该项目。

然后可以将过早的列表结束作为异常捕获。

该算法将完全相同，但实现应该更高性能。

更新：事实证明它实际上不是（大约两倍的时间）。哦，好吧，知道可能有用。

在对不同场景进行基准测试时，事实证明，除非指定三个字符串长度是“精确的”（即 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)

然后我在随机字符串上运行了一些基准测试，这就是仪器（注意它总是生成有效的随机播放，这可能会产生有偏差的结果）：

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)

结果似乎表明缓存+DP算法对于短字符串的效率更高。当字符串变长（超过 3-4 个字符）时，缓存+DP 算法开始失势。在长度约为 10 时，上述算法的执行速度是完全递归的缓存版本的两倍。

如果字符串包含重复字符（我通过限制从 az 到 ai 的范围来做到这一点）并且重叠很小，则 DP 算法的性能更好，但仍然比上述算法差。例如，在这种情况下，DP 仅损失 2us：

(cfccha,ddehhg = cfcchaddehhg) in 68.139601 against 66.826320 us

毫不奇怪，完全重叠（每个字符串依次一个字母）的差异更大，比率高达 364:178（略高于 2:1）。

于 2012-09-23T22:27:20.833 回答
0

首先，只是一个实现点：我认为您可能会摆脱对 str1 和 str2 长度的测试。在 C 中，字符串以 nul 字符结尾，所以这个特殊字符永远不会在 str3 中找到。所以只要p1++找到正确的字符就可以了。但是在 python 中，我不记得这个功能是否存在......对不起，我不是一个认真的 python 用户。如果 p1==len(p1)，str1[p1] 的输出是什么？

除此之外，正如 Jirka Hanika 所指出的，您的代码输出是错误的。我见过另一种失败的情况：如果一个字符在两个子字符串中都是通用的。例如：如果 str1="abc", str2="dbe"，则 str3="adbec" 包含 str1 和 str2，但您的算法在这种情况下失败。问题来自elif语句，而不是另一个 if。

Iserni 的代码输出在我看来是正确的。

于 2012-09-24T08:57:45.397 回答