[LeetCode/Go] 14.Longest Common Prefix

概要

以下の問題の個人的メモです。
https://leetcode.com/problems/longest-common-prefix/

問題概要

複数のワードが入ったスライスが渡されるので、それらに共通する接頭辞を取り出す問題。
たとえば ["prefix", "pride", "proud"] のとき pr。

解法

初見

ポインタを用意し、すべての単語について頭からチェックしていく。相違があれば終了。
後述の垂直スキャンと発想は同じだった。

Go に Set はないので map で代用。
時間計算量は $O(MN)$（Mは最大文字数、Nは単語数）、空間計算量は $O(N)$（たぶん）。

func getLongestWordLength(strs []string) int {
    var m, lb int
    for _, w := range strs {
        lb = len(w)
        if m < lb {
            m = lb
        }
    }
    return m
}

func longestCommonPrefix(strs []string) string {
    var p string
    ml := getLongestWordLength(strs)
    for i:=0; i<ml; i++ {
        m := make(map[byte]bool, len(strs))
        for _, w := range strs {
            if len(w) <= i {
                return p
            }
            m[w[i]] = true
        }
        if len(m) != 1 {
            break
        }
        p += string(strs[0][i])
    }
    return p
}

水平スキャン（Horizonal Scanning）

頭の2つを比較し接頭辞を取得、それと次の単語を比較し接頭辞を取得...みたいな感じで、2つずつ比較して解決していくパターン。時間計算量は $O(N)$、空間計算量は $O(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
}

垂直スキャン（Vertical Scanning）

すべての単語の文字を頭から検査していくパターン。
時間計算量 $O(N)$、空間計算量 $O(1)$ 。処理速度も基本は水平スキャンと同じだが、配列の末尾近くに最短の単語がある場合、こちらの方が早い。

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    for i := 0; i < len(strs[0]); i++ {
        c := strs[0][i]
        for j := 1; j < len(strs); j++ {
            if i == len(strs[j]) || strs[j][i] != c {
                return strs[0][:i]
            }
        }
    }
    return strs[0]
}