多少単純なアプローチは、各単語のすべての最初の文字のマルチセットを検索し、最初の文字のマルチセットとまったく同じ文字と文字カウントを含む単語を検索します。一致するものが見つかった場合は、その単語を考慮から除外します。次に、接尾辞(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!)
に比べて改善です。
通常通り繰り返して文字列を作成します。もう一方の方法を反復して別の文字列を作成します。 2つの文字列を比較します。 – ifly6