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つはそれで始まるため、それが答え全体です。共通の接頭辞が最も短い単語より長くなることはありません。
提出時に隠しテスト+19件
発展問題
リストは固定されたままで、検索する単語が多数あるとします。リストを毎回再走査することなく、各検索語について、リスト内の少なくとも1つの単語と共有する最長の接頭辞をどのように見つければよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
答えは、最も短い単語より長くなることはありません。それに含まれる各文字は、どのような条件を満たす必要がありますか？
位置
iの文字が答えに含まれるのは、すべての単語に位置iの文字があり、それらがすべて同じ場合に限ります。その条件を満たさなくなる最初の位置で、答えは終わります。- 最初の単語の位置を左から右へ順に確認します。各位置で、ほかのすべての単語を確認し、いずれかの単語が短すぎるか、異なる文字があれば、その位置より前の最初の単語の部分を返します。
解説
ある文字が答えに含まれるのは、すべての単語で同じ位置にその文字がある場合に限られます。また、どれかの単語で文字が異なるか、文字がなくなる最初の位置で答えは終わります。以下の2つの方法はいずれも単語を1文字ずつ読みますが、読む順序が異なります。列ごとに調べる方法は最初に不一致が見つかった時点で止まるため、答えに加えて1列分より先まで読むことはありません。
接頭辞を単語ごとに短くする
考え方
まず、最初の単語全体が答えだと仮定します。次に、2番目の単語と文字ごとに比較し、共通する部分だけになるまで短くします。残った部分を3番目の単語と比較し、同様に続けます。最後の単語まで比較した後に残る部分が、すべての単語に共通する部分です。
これは、複数の単語に共通する接頭辞が、最初の2つの単語の共通接頭辞、次にその結果と3番目の単語の共通接頭辞、というように求められるため、正しい方法です。各ステップで接頭辞は維持されるか短くなるだけです。interview、internet、interval、internalの場合、候補は2番目の単語を比較した後にinterviewからinterになり、そのまま変わりません。
各文字は最大1回しか比較されないため、時間計算量はO(S)です。ここでSは文字の総数です。保持するのは長さだけで、コピーはしません。弱点は順序です。最初の199個の単語が一致し、最後の単語だけが先頭の文字で異なる、200文字の単語が200個ある場合、最後の単語によって接頭辞が空になるまでに、最初の199個の単語それぞれについて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]列ごとに比較する
考え方
単語を表のように、列ごとに読みます。列 0 にはすべての単語の最初の文字が、列 1 には2番目の文字が入り、以降も同様です。現在の列にある strs[0] の文字を取り出し、ほかのすべての単語もその位置に同じ文字があるか確認します。単語の文字が初めて一致しない場合、またはその列まで文字がないほど短い場合、答えはその列までの strs[0] です。
答えは、すべての単語が一致する列の連続部分そのものです。このループは左から列をたどり、その連続部分が途切れる最初の列で停止します。どの列でも途切れなければ、strs[0] 自体が答えです。この場合、これは最短の単語か、それと同じ長さの単語です。
このループが読むのは、答えの直後の列までです。そのため、単語が n 個あり、答えの長さが L の場合、チェック回数は最大で n × (L+1) 回です。また、各単語の同じ文字を2度読むことはないため、計算量は O(S) でもあります。上記のケースでは、199個の単語が一致し、最後の単語が最初の文字で異なるため、最初の列を確認した時点で停止します。比較回数は約40,000回ではなく、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)だけです。列方向の走査はn × (L+1)によっても上限が決まります。ここでLは答えの長さです。そのため、単語が先頭付近で一致しない場合は早く終了します。
単語を並べ替えて、最長共通接頭辞を見つけられますか？
はい。アルファベット順では、最初と最後の単語の間にあるすべての単語は、その2つの単語に共通する文字で始まるため、最初と最後の単語だけを比較すれば答えが得られます。ソートでは約n log n組の単語を比較するため、1回の走査よりコストがかかりますが、コードは短くなります。
共通の接頭辞がない場合、Longest Common Prefix は何を返すべきですか？
空文字列 "" を返します。stack、queue、heap のように、2つの単語が異なる文字で始まると、すぐにそうなります。
水平走査と垂直走査では、どちらが優れていますか？
どちらも最悪計算量は同じで、O(S)です。縦方向に列ごとに走査するほうが安全な選択です。どれか1つの単語が一致しない最初の列で停止しますが、横方向に走査すると、後ろの単語によって途中で打ち切られるまで、多くの単語に対して長い接頭辞を比較することがあります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def longestCommonPrefix(strs):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
strs = ["interview", "internet", "interval", "internal"]
期待値
"inter"