2016-10-19 9 views
2

明らかに、これはGoogleの友人に質問された質問です。疑問は、4文字の4語が与えられた場合、それが単語の正方形を形成するかどうかを決定することです。次にn n文字の単語に対して解くことができるように展開します。ワード広場の例は次のようになります。私たちが考えることができ単語リストが単語を構成するかどうかを判断するアルゴリズム

CATS

ABEO

TELM

SOME

最も簡単な方法は、O(N!)だったすべてを試すために単語構成の可能な順列、次にO(n)が単語の正方形を形成するかどうかをチェックする。対角線の一方の側が他方と等しいかどうかをチェックすることによって行うことができる。

+0

通常通り繰り返して文字列を作成します。もう一方の方法を反復して別の文字列を作成します。 2つの文字列を比較します。 – ifly6

答えて

0

(これはプログラムの作成に使用するアルゴリズムですが、これはプログラムでは非常に簡単ですが、明らかに人がそれを描くことができれば、あなたが好きなら、これを行うJavaプログラムを書くことができます。)

1)各単語の最初の文字の最初の列を第1列にし、最初の行を最初の言葉から構成されています。次に、最初の列は最初のワードに等しいかどうかを確認

CATS

ABEO SOME

TELM

)、2番目の列は第2のワードに等しく、そうで。 (最初の行が文字通り最初の単語であるため、最初の列が最初の単語と等しいかどうかを確認するために、基本的に最初の行が最初の列と等しいかどうかを確認します)。

0

多少単純なアプローチは、各単語のすべての最初の文字のマルチセットを検索し、最初の文字のマルチセットとまったく同じ文字と文字カウントを含む単語を検索します。一致するものが見つかった場合は、その単語を考慮から除外します。次に、接尾辞(2番目の文字で始まる)が残りの単語の2番目の文字の集合と一致する単語を探します。一致するものが見つかった場合はそれを削除し、3番目の文字を確認します。

ここには、マルチセットの代わりにcollections.Counterクラスを使用するPythonの実装があります。

from collections import Counter 

def word_square(words): 
    words = list(words) 
    n = len(words) 
    assert all(len(w) == n for w in words) 

    result = [] 

    for i in range(n): 
     letters = Counter(w[i] for w in words) 
     match = next((w for w in words if Counter(w[i:]) == letters), None) 

     if not match: 
      return None 

     words.remove(match) 
     result.append(match) 

    return result 

私間違っていないが、素晴らしいではありませんこれは、O(n^3)であれば、このソリューションは、ですが、それはO(n!)に比べて改善です。

関連する問題