Python 2.7ある文字列のアナグラムが別の文字列の部分文字列であるかどうかを調べる

Question

EDIT：これは非常に有用なスレッドであったため、最終的な解決策を投稿しました。以下の両方の答えのアドバイスを使用して、私は解決策を作ることができました。私はアナグラムを定義したヘルパー関数を追加しました。ここに私の最終的な解決策である：

def anagram(s1, s2): 
    s1 = list(s1) 
    s2 = list(s2) 
    s1.sort() 
    s2.sort() 
    return s1 == s2 

def Question1(t, s): 
    t_len = len(t) 
    s_len = len(s) 
    t_sort = sorted(t) 
    for start in range(s_len - t_len + 1): 
     if anagram(s[start: start+t_len], t): 
      return True 
    return False 

print Question1("app", "paple") 

---

私はいくつかの練習の技術的なインタビューの質問に取り組んでいると私は、次の質問にこだわっている：私は次のように働いている

Find whether an anagram of string t is a substring of s

私のコードの2つの変種、そして私はこの2つの間のクロスにあると信じています。私が抱えている問題は、入力にかかわらず、最初のコードは常にFalse.を出力するということです。 2つ目のバリエーションはある程度機能します。ただし、個々の文字をソートすることはできません。私はこの二つの間にある解決策があると信じているが、私はどのように考え出すのトラブルを抱えている

def Question1(): 
    # Define strings as raw user input. 
    t = raw_input("Enter phrase t:") 
    s = raw_input("Enter phrase s:") 
    # use a loop to find if t is in s. 
    if t.lower() in s.lower(): 
     print("True!") 
    else: 
     print("False.") 

Question1() 

：印刷されますたとえばt=jks s=jksdについてTrue!しかしt=kjs s=jksdはFalse.

def Question1(): 
    # Define strings as raw user input. 
    t = raw_input("Enter phrase t:") 
    s = raw_input("Enter phrase s:") 
    # Use the sorted function to find if t in s 
    if sorted(t.lower()) in sorted(s.lower()): 
     print("True!") 
    else: 
     print("False.") 

Question1() 

ワーキング・バリアントを印刷しますこの状況でsortedを使用してください。

Answer 1

あなたは正しい軌道に乗って大変です。まず、2回目の試行でループがないことに注意してください。

問題は、すべてのsを並べ替えてからsorted（t）を検索することができないという問題です。むしろ、sの各len（t）サブストリングを考慮し、ソートされたtに対してであるをチェックする必要があります。簡単な例を考えてみましょう：

t = "abd" 
s = "abdc" 

のは自明トンが含まれています。ただし、ソートすると文字列が得られますabdとabcd比較が失敗します。ソートは途中で他の文字を取得します。

代わりに、のには、のサイズがのチャンクが必要です。

t_len = len(t) 
s_len = len(s) 
t_sort = sorted(t) 
for start in range(s_len - t_len + 1): 
    chunk = s[start:start+t_len] 
    if t_sort == sorted(chunk): 
     # SUCCESS!! 

Answer 2

あなたの問題は「部分文字列」要件にあると思います。ソートすると、オーダーが破棄されます。つまり、string1のアナグラムがstring2の部分文字列のアナグラムであると判断できるのに対して、実際にstring2を順番に処理するまでは、正しい答えはありません。

長さがlen(s1)のすべての部分文字列を反復することをお勧めします（s2）。これは単純なforループです。部分文字列を取得したら、s1でそれらを比較して（ソート済みかソート済みか）、s1の並べ替えがあり、隣接する部分文字列がs2になるかどうかを判断できます。

ビズ：

s1 = "jks" 
s2 = "aksjd" 

print('s1=',s1, ' s2=', s2) 
for offset in range(len(s2) - len(s1) + 1): 
    ss2 = s2[offset:offset+len(s1)] 
    if sorted(ss2) == sorted(s1): 
     print('{} is an anagram of {} at offset {} in {}'.format(ss2, s1, offset, s2))