🖋
LeetCode 14. Longest Common Prefix
はじめに
LeetCode 「14. Longest Common Prefix」の問題をGoで解きました。
問題
問題文
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
和訳
文字列の配列から最長の共通接頭辞文字列を見つける関数を書く。
共通の接頭辞がない場合は、空の文字列 "" を返す。
例
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
制約
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters if it is non-empty.
解答
配列から最長の共通接頭辞を求める問題です。
最初の文字列を基準に、各文字の位置（インデックス）を順に比較していきます。
外側のループではインデックス i を進めながら、
内側のループで他の文字列の同じ位置の文字と比較します。
次のいずれかの条件を満たした時点で不一致とみなし、
それまでに一致していた部分（接頭辞）を返します。
- i が対象の文字列の長さ以上になった場合（文字が存在しない）
- 同じ位置の文字が一致しなかった場合
コード
func longestCommonPrefix(strs []string) string {
for i := 0; ; i++ {
if i >= len(strs[0]) {
return strs[0]
}
ch := strs[0][i]
for j := 1; j < len(strs); j++ {
if i >= len(strs[j]) || ch != strs[j][i] {
return strs[0][:i]
}
}
}
}
計算量
- 時間的計算量：O(mn)
- 外側ループ最大回数 m回
- 内側ループ最大回数 n-1回 （O(n)とみなす）
- 空間的計算量：O(1)
Discussion