2022/03/30

Leetcode Note: Go - Longest Common Prefix

Longest Common Prefix - LeetCode
https://leetcode.com/problems/longest-common-prefix/

  • Go 言語で取り組んだメモ

所感

  • input された各種 string 情報を全部走査して愚直に実装すれば良さそう

実装準備

func longestCommonPrefix(strs []string) string {
    return "Hello"
}

func main() {
    input := []string{"flower","flow","flight"}
    fmt.Println(input)

    output := longestCommonPrefix(input)
    fmt.Println(output)
}

配列の各要素の先頭文字列から一致しているかを確認するには

  • strs をループで全て走査しつつ、それらを最小文字列分ループするのがシンプルそう

最小文字列数を取得

    minLength := 201
    for i := 0; i < len(strs); i++ {
        if len(strs[i]) < minLength {
            minLength = len(strs[i])
        }
    }
  • 問題の制約上、最大文字列は 200 なので 201 より小さいものを順に代入すれば良さそう
    • もっと良い実装方法ありそうだが・・・

各種文字列の先頭を比較していく

	// 各 string の先頭文字から一致するか比較
	// 最小文字列をスコープとしてループ
	for i := 0; i < minLength; i++ {
		var currentChar string

		// 各文字を比較
		for _, str := range strs {

			// 比較する文字列の初期化処理
			if currentChar == "" {
				currentChar = string(str[i])
				continue
			}

			if string(str[i]) != currentChar {
				return output
			}
		}

		output += string(currentChar)
	}

回答

func longestCommonPrefix(strs []string) string {
	output := ""

	// strs の中で最小文字列長を特定
	minLength := 201
	for i := 0; i < len(strs); i++ {
		if len(strs[i]) < minLength {
			minLength = len(strs[i])
		}
	}

	// 各 string の先頭文字から一致するか比較
	// 最小文字列をスコープとしてループ
	for i := 0; i < minLength; i++ {
		var currentChar string

		// 各文字を比較
		for _, str := range strs {

			// 比較する文字列の初期化処理
			if currentChar == "" {
				currentChar = string(str[i])
				continue
			}

			if string(str[i]) != currentChar {
				return output
			}
		}

		output += string(currentChar)
	}

	return output
}

これで Pass できた

See Also