🔖

LeetCode 14-longest-common-prefix - 垂直スキャンと水平スキャン

2025/08/09に公開

LeetCode

tech

14-longest-common-prefix

アプローチ

失敗したアプローチ

最初にrubyではそれぞれの文字列の重複をとればいいかと考えた。

ruby

配列の共通要素を取得する。

> "flower".chars & "flight".chars
=>  ["f", "l"]

# 以下のテストケースが通らないためNG
# strs =["cir","car"]
# Output: "cr"
# Expected: "c"
def longest_common_prefix(strs)
  strs[1..].reduce(strs[0].chars) do |acc, str| acc & str.chars end.join
end

配列の共通要素を見つけてしまっている、共通の接頭辞を見つける必要がある。
1文字ずつ評価する必要があるのかと考える。文字列の配列にして、列ごとに比較する方式を検討。

垂直方向のスキャン

strs.map(&:chars)
=> [["f", "l", "o", "w", "e", "r"], ["f", "l", "o", "w"], ["f", "l", "i", "g", "h", "t"]]
strs[0].chars.zip(*strs[1..].map(&:chars))
=> [["f", "f", "f"], ["l", "l", "l"], ["o", "o", "i"], ["w", "w", "g"], ["e", nil, "h"], ["r", nil, "t"]]

文字列の配列にして、列ごとに比較する方式を検討

strs[0].chars.zip(*strs[1..].map(&:chars)).inject("") do |acc, columns|
  if  columns.all?(columns[0])
    acc + columns[0]
  else 
    break acc
  end
end

文字列が一致しないタイミングでreduceメソッドをbreakによって抜ける際に結果を返却する。そうしないと、["cir","car"]のときに"cr"となってしまう。

python

rubyからpythonコードへ変換
reduceよりforループを使ったほうがpythonでは読みやすい

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix =""
        for col_chars in zip(*strs):
            if len(set(col_chars)) == 1:
                prefix += col_chars[0]
            else:
                break
   		return prefix

水平方向のスキャン

typescript

typescriptではzip関数がないため自作する必要があるため、水平方向のスキャンで実装する
indexOf https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/indexOf
- インスタンスメソッドindexOf()はArray、配列内で指定された要素が見つかる最初のインデックスを返します。存在しない場合は -1 を返します。

const beasts = ["ant", "bison", "camel", "duck", "bison"];

console.log(beasts.indexOf("bison"));
// Expected output: 1

slice https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/slice
- 後ろから1文字ずつ削るようにする
- 現在のprefixがstrs[i]の接頭辞になるまで、prefixの末尾から1文字ずつ削ります

const strs = "ant"

console.log(strs.slice(0, strs.length -1));
// Expected output: "an"

1文字ずつループして末尾から削る
最初の文字列を基準に、他の文字列に合わせて接頭辞を削る

function longestCommonPrefix(strs: string[]): string {
    let prefix = strs[0]

    for (let i = 1; i < strs.length; i++){
        // 現在のprefixがstrs[i]の接頭辞になるまで、prefixの末尾から1文字ずつ削ります
        // str[1]="flow"の場合は、prefixが"flow"になるまで1文字ずつ削る
        while (strs[i].indexOf(prefix) != 0){
            prefix = prefix.slice(0, prefix.length -1);
            if (prefix === "") return ""
        }
    }
    return prefix
};

golang

スライス
- prefix[:len(prefix)-1] は、文字列の最後の1文字を削除するためのものです。

func main() {
    prefix := "prefix"
    fmt.Printf(prefix[:len(prefix)-1])
    // prefi
}

最初の文字列を基準に、1文字ずつ他の文字列と比較する

func longestCommonPrefix(strs []string) string {
    prefix := strs[0]
    for i:=1; i<len(strs); i++ {
        for strings.Index(strs[i], prefix) != 0 {
            prefix = prefix[:len(prefix)-1]
            if prefix == ""{
                return ""
            }
        }
    }
    return prefix
}

c++

C++でも同様に水平スキャンで実装します。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = strs[0];
        for (int i = 1; i<strs.size(); i++){
            while(strs[i].find(prefix) != 0){
                prefix = prefix.substr(0, prefix.length() - 1);
                if (prefix.empty()) return "";
            }
        }
        return prefix;
    }
};

学びのポイント

アルゴリズムの選択: 同じ問題でも、言語の標準ライブラリや特性によって実装しやすいアルゴリズムが異なります（例: Ruby/Pythonのzip vs 他言語のループ）。
垂直スキャン vs 水平スキャン:
- 垂直スキャン: 接頭辞が短い場合に効率的です。最初の数文字で不一致が見つかれば、すぐに処理を終えられます。
- 水平スキャン: 文字列の数が少ない場合に効率的です。最初の文字列が極端に長いと、多くの文字列比較が無駄になる可能性があります。