Longest Common Prefix
単語の配列 strs が与えられます。すべての単語の先頭に共通する最長の文字列を返してください。すべての単語が同じ文字で始まらない場合は、空文字列 "" を返してください。単語はそれ自体の接頭辞とみなされるため、単語が1つだけの場合はその単語が答えになります。
関数
- strsstring-array
- 比較する語
- 戻り値string
- すべての単語に共通する最長の接頭辞、または空文字列
制約
1 ≤ strs.length ≤ 2001 ≤ strs[i].length ≤ 200- すべての単語は、小文字の英字のみで構成されています。
例
- 入力
- strs = ["interview", "internet", "interval", "internal"]
- 出力
- "inter"
- 説明
- 4つの単語はすべて
interで始まります。次の位置では、interviewとintervalはvを持ち、internetとinternalはnを持つため、接頭辞はそこで終わります。
- 入力
- strs = ["stack", "queue", "heap"]
- 出力
- ""
- 説明
- 単語は
s、q、hで始まります。最初の文字から異なるため、答えは空です。
- 入力
- strs = ["prefix", "pre", "prepare"]
- 出力
- "pre"
- 説明
preは最も短い単語で、他の2つはそれで始まるため、それが答え全体です。共通の接頭辞が最も短い単語より長くなることはありません。
発展問題
リストが固定されたまま、多くの検索語が次々に与えられるとします。リストを再走査せずに、各検索語について、リスト内のいずれかの単語と共有する最長の接頭辞をどのように見つけますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
答えが最も短い単語より長くなることはありません。それに含まれる各文字について、何が成り立っていなければなりませんか？
位置
iの文字が答えに含まれるのは、すべての単語に位置iの文字があり、それらがすべて同じ場合に限ります。答えは、それが成立しなくなる最初の位置で終わります。最初の単語の各位置を左から右へたどります。各位置で、ほかのすべての単語を確認します。単語が短すぎるか、異なる文字が見つかったら、その位置より前の最初の単語の部分を返します。
解説
ある文字が答えに含まれるのは、すべての単語の同じ位置にその文字がある場合に限られ、答えは単語同士が初めて食い違うか、単語の長さが尽きる位置で終わります。どちらの方法も、単語を文字ごとに異なる順序で読み取ります。列ごとに調べる方法では、最初の食い違いで終了します。
接頭辞を単語ごとに短くする
考え方
最初の単語全体が答えだと仮定します。それを2番目の単語と共通する部分まで短くし、次に3番目の単語と共通する部分まで短くし、以降も同様にします。複数の単語に共通する接頭辞は、最初の2つの単語に共通する接頭辞に、さらに3番目の単語との共通部分を加えていくことで求められます。各ステップで接頭辞は維持されるか短くなるだけです。たとえば例1では、候補は2番目の単語の後にinterviewからinterになり、そのまま維持されます。
各文字は最大1回しか比較されないため、すべての文字数をSとすると、時間計算量はO(S)です。弱点は順序です。最初の文字だけが異なる最後の単語まで、200文字の単語が200個ある場合、最後の単語によって接頭辞が空になるまでに、約40,000回比較することになります。
アルゴリズム
prefixLenをstrs[0]の長さに設定します。- ほかの各単語について、
prefixLenまでの範囲で、先頭から何文字がstrs[0]と共通しているかを数えます。 prefixLenをその数に設定し、0になったらそこで処理を終了します。strs[0]の先頭からprefixLen文字を返します。
def longestCommonPrefix(strs):
first = strs[0]
prefix_len = len(first)
for word in strs[1:]:
common = 0
while common < prefix_len and common < len(word) and word[common] == first[common]:
common += 1
prefix_len = common
if prefix_len == 0:
break
return first[:prefix_len]列ごとに比較する
考え方
単語を表のように、列ごとに読んでください。現在の列にあるstrs[0]の文字を取り出し、ほかのすべての単語の同じ位置に同じ文字があるか確認します。単語の文字が初めて一致しなくなるか、その列まで文字がないほど短い単語が見つかったら、答えはその列までのstrs[0]です。
答えは、すべての単語の文字が一致する列が連続する部分そのもので、このループはその部分を左からたどり、一致しなくなったところで停止します。一致しなくなる箇所がなければ、答えはstrs[0]です。
n個の単語があり、答えの長さがLの場合、ループが行う確認は最大でもn × (L+1)回で、これはO(S)でもあります。200個の単語のうち最後の単語だけが最初の文字で異なる場合、199回の比較を行ったところで停止します。
アルゴリズム
firstをstrs[0]とします。colが0からfirstの長さから1を引いた値までの各列について、first[col]を読み取ります。- ほかの各単語について、
colの位置に文字がない場合、またはその文字が異なる場合は、firstの先頭からcol文字を返します。 - すべての列が一致する場合は、
firstを返します。
def longestCommonPrefix(strs):
first = strs[0]
for col in range(len(first)):
for word in strs[1:]:
if col == len(word) or word[col] != first[col]:
return first[:col]
return first
落とし穴と境界ケース
- 短い単語の末尾を越えて読み取ること。
prefix、pre、prepareでは、列3はprefixにはありますが、preにはありません。文字を読み取る前に長さを確認しましょう。 - 並べ替えずに、最初と最後の単語だけを比較すること。
abc、xbd、abdでは、最初と最後の単語はabを共有していますが、xbdが列0で一致しないため、答えは空になります。 - 共通部分がないときに
nullやプレースホルダーを返すこと。答えは空文字列です。 - 1つの単語はそれ自体が接頭辞であることを忘れること。
algorithmだけの場合は、algorithmを返します。 - 不変文字列に1文字ずつ追加すること。答えが200文字の場合、200回のコピーが必要になります。長さを保持し、最初の単語から一度だけ切り出しましょう。
よくある質問4
最長共通接頭辞の時間計算量はどのくらいですか？
どちらの走査も O(S) 時間で実行されます。ここで S は文字の総数であり、答えを除けば追加メモリは O(1) です。列方向の走査は、長さ L の答えに対して n × (L+1) にも制限されるため、単語が先頭付近で一致しない場合は早期に終了します。
単語を並べ替えて、最長共通接頭辞を見つけられますか？
はい。アルファベット順では、最初と最後の単語の間にあるすべての単語は、この2つに共通する文字から始まるため、この2つだけを比較すれば答えがわかります。ソートではおよそn log n組の単語を比較するため、1回スキャンするよりコストがかかりますが、コードは短くなります。
共通の接頭辞がない場合、Longest Common Prefix は何を返すべきですか？
空文字列 ""。これは、stack、queue、heapのように、2つの単語が異なる文字で始まるとすぐに起こります。
横方向の走査と縦方向の走査では、どちらが優れていますか？
どちらも最悪計算量は同じで、O(S)です。縦方向の走査のほうが安全な選択です。どれかの単語が一致しない最初の列で停止する一方、横方向の走査では、後の単語によって打ち切られるまで、長い接頭辞を多数の単語と比較することがあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def longestCommonPrefix(strs):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
strs = ["interview", "internet", "interval", "internal"]
期待される出力
"inter"