アルゴリズムの復習：最長共通接頭辞

トピックの分析

まず、タイトルを見た方がいいです：

例1.

b:
    [
        'flower',
        'flow',
        'flight'
    ];
bar:
    'fl';

例2.

obj:
    [
        'dog',
        'racecar',
        'car'
    ];
bar:
    '';

説明

• 入力には公開接頭辞がありません。

説明

• すべての入力には、小文字の a ～ z のみが含まれます。

問題分析

最長の共通接頭辞を求めるには、まず接頭辞を公開し、どの要素からも求めることができるようにします。配列から最長の共通接頭辞を探すとすると、まず最初の要素を基底要素 x0 とします。 配列が ["flow", "flower", "flight"] の場合、 flow が基底要素 x0 となります。

そして、ベンチマーク要素とそれに続く要素を順番に比較し、ベンチマーク要素とすべての要素が最長共通接頭辞の条件を満たすまでベンチマーク要素を更新し続け、最長共通接頭辞を求めればよいのです。

具体的な比較の流れは以下の通り：

• もしstrings.Index(x1,x) == 0なら、直接スキップして次の要素を比較します。
• もしstrings.Index(x1,x) ！= 0 の場合、ベース要素 x の最後の要素をインターセプトし、strings.Index(x1,x) == 0 になるまで再度 x1 と比較します。

プロセスを以下に示します：

なお，ベースライン要素の処理において，ベースライン要素とどちらかの要素が一致しない場合は，最も長い共通要素がないことを意味します．

最後に、臨界条件を扱うことを忘れないでください。もし与えられた配列が空であれば、それは最も長い共通要素がないことを意味します。

それからコードを書き始めることができます。

コード解析

この分析に基づけば、次のような解答を得ることは容易です：

//GO
func longestCommonPrefix(strs []string) string {
 if len(strs) < 1 {
 return ""
 }
 prefix := strs[0]
 for _,k := range strs {
 for strings.Index(k,prefix) != 0 {
 if len(prefix) == 0 {
 return ""
 }
 prefix = prefix[:len(prefix) - 1]
 }
 }
 return prefix
}

走行結果

もちろん、パーティション分割や他の方法でこの質問に答えることもできます。自分で試してみてください。それではまた次号で！

私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。クリックしてダウンロード