python - 在 python 中查找字符串的有效方法

Question

You are given two strings, AA and BB. Find if there is a substring that appears in both AA and BB.

All the strings contain only lowercase Latin letters.

上面，你看到a question from hackerranck .我写了下面的程序来解决它:

T = int(raw_input())

for t in xrange(T):
    s1 = raw_input()
    s2 = raw_input()
    length1 = len(s1)
    length2 = len(s2)
    checked = list()
    if length1<length2:
        for letter in s1:
            if len(checked)== 26:
                break
            if letter in checked:
                next
            checked.append(letter)
            if letter in s2:
                print "YES"
                break
        else:
            print "NO"
    else:
        for letter in s2:
            if letter in checked:
                next
            if len(checked)==26:
                break
            checked.append(letter)
            if letter in s1:
                print "YES"
                break
        else:
            print "NO"

在添加 if len(checked)==26: break 之前它工作正常。我添加这一行是为了通过只检查每个字母一次并消除提交过程中的超时错误来提高效率，但是在添加这一行之后，我的程序的答案对于某些测试用例是错误的。为什么？

Answer 1

你的错误在这里:

if letter in checked:
    next

next is a function在 Python 中。使用 if letter in checked: next 是空操作，您也可以使用 pass，因为它只会引用函数对象而不调用它。它肯定不会继续到下一个循环迭代。

因此无论letter in checked 的结果如何，您都继续将letter 添加到checked .由于 checked 是一个列表，而不是一个集合，您将向列表中添加重复项，很容易得到超过 26 个条目。

使用:

if letter in checked:
    continue

并考虑使用一组 checked 来使 in 成员资格测试成为 O(1) 操作而不是 O(N)。

说到集合，这基本上是一个集合交集问题； s1 和 s2 中是否有任何单个字母出现。您正在正确测试这些集合是否不相交；所以使用 Python built-in set type .这在最坏的情况下会执行 O(N * M) 循环，但循环是在 C 代码中:

print('NO' if set(s1).isdisjoint(s2) else 'YES')

通过使用 set.isdisjoint()没有创建新集，只返回一个 bool 值。 set(s1) 遍历所有 s1 以生成集合，set.isdisjoint() 将在找到匹配项后立即退出，每个匹配测试都是针对集合的 O(1)。

你可以看看根据长度交换 s1 和 s2 是否仍然可以改善你的测试时间:

if len(s1) > len(s2):
    s1, s2 = s2, s1
print('NO' if set(s1).isdisjoint(s2) else 'YES')