Leetcode Note: Go - Word Pattern

Word Pattern - LeetCode
https://leetcode.com/problems/word-pattern/

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

所感

  • string 型の pattern, s が引数として渡ってくる
    • pattern: 文字列で判定したいパターン
      • bijection (全単射) かを判定する
    • s: 文字列

回答

Go Solution Map and Array - 0ms - LeetCode Discuss
https://leetcode.com/problems/word-pattern/discuss/834338/Go-Solution-Map-and-Array-0ms

func wordPattern(pattern string, s string) bool {
	codes := make(map[string]byte)
	used := make([]bool, 26)
	words := strings.Split(s, " ")

	// 単語とパターン数が異なれば false
	if len(pattern) != len(words) {
		return false
	}

	// 単語数をループ
	for i, word := range words {
		// codes[word] に値があるかチェック
		code, ok := codes[word]

		// codes[word] に値が無い
		if !ok {
			// 文字が既に使用されているかチェック
			if used[pattern[i]-'a'] {
				return false
			}

			// 文字を使用したことをマーク
			used[pattern[i]-'a'] = true

			// codes[word] に pattern[i] を格納
			codes[word] = pattern[i]

			// ループ継続
			continue
		}

		// codes[word] が pattern[i] と異なれば false
		if code != pattern[i] {
			return false
		}
	}

	return true
}
  • codes, used という 2つ の配列を使ってステートを管理
    • codes: パターンを管理するマップ
      • word に対する pattern を記録
      • 同じ word なら同じ code として判定する
    • used: 文字を使ったか管理する配列
      • index: pattern[i] - 'a'
        • pattern は string だが配列アクセスすると uint8 として扱われる
        • uint8 の数値から - 'a' すると良い感じの数値になる
          • 'a' が uint8 としては 97 であり、 b は 98 、 c は 100 と続いていくので、アルファベットを 0 スタートの数値に変換できるという仕組み
          • 今回の場合 used は length 26 の bool 配列のため、取り回しが良い
      • true: 使った
      • false: 使ってない