効率的な方法でPythonの文字列を見つける

Question

あなたは2つの文字列AAとBBが与えられます。 AAとBBの両方に表示される部分文字列 があるかどうかを調べます。

すべての文字列には、小文字のラテン文字のみが含まれています。

以上、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を追加する前に、正しい働いていました。この行を追加すると、各英字を1回だけチェックして、送信プロセスのタイムアウトエラーを取り除くことができますが、この行を追加すると、プログラムの答えはいくつかのテストケースで間違っています。どうして？

Answer 1

あなたのエラーはここにある：Pythonで

if letter in checked: 
    next 

next is a function。 if letter in checked: nextを使用することはノーオペレーションです。passを使用しただけでも、関数オブジェクトを参照して呼び出すことはありません。それは確かに次のループの反復にcontinueしません。

のでどんなにletter in checkedの結果はあなたがcheckedにletterを追加していく、何ですか。 checkedはセットではなくリストであるため、リストに重複を追加することになり、26個以上のエントリがかなり簡単に終了します。

使用：

if letter in checked: 
    continue 

むしろO（N）よりもO（1）の動作をテストinメンバーシップを作るためにcheckedためのセットの使用を検討してください。

といっても、これは基本的に交点の問題です。 s1とs2の両方に現れる単一の文字があります。セットがばらばらになっているかどうかを正しくテストしています。 Python built-in set typeを使用してください。これは、最悪の場合にはO（N * M）ループを行うだろうが、ループは、Cコードである：

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

だけブールが返され、新しいセットが作成されていないset.isdisjoint()を使用することにより。 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') 

Answer 2

あなたはセットを使用し、交差点がゼロよりも大きいかどうかを確認することができます

"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"