在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

可以使用集合并查看交点是否大于零：

"yes" if set(s1).intersection(s2) else "no"

要避免重复整个列表：

"yes" if any(c in s1 for c in s2) else "no"

根据s1和s2的大小，将它们缩小为一组可能会有好处：

"yes" if any(c in set(s1) for c in set(s2)) else "no"

Answer 2

您的错误如下：

if letter in checked:
    next

^{} is a function在Python中。使用if letter in checked: next是不可行的，您也可以使用pass，因为这样只会引用函数对象而不会调用它。它当然不会continue到下一个循环迭代。你知道吗

所以，不管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(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')