🖋
LeetCode 290. Word Pattern
はじめに
LeetCode 「290. Word Pattern」の問題をGoで解きました。
問題
問題文
Given a pattern and a string s, find if s follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s. Specifically:
- Each letter in
patternmaps to exactly one unique word in s. - Each unique word in
smaps to exactly one letter inpattern. - No two letters map to the same word, and no two words map to the same letter.
和訳
patternと文字列 s が与えられたとき、s が同じpatternに従うかどうかを調べる。
ここで、続くとは完全一致を意味し、pattern中の文字と s 中の空でない単語との間に双射が存在するようなものである：
-
pattern内の各文字は、s 内の 1 つの一意の単語に正確にマッピングされる。 -
s内の各一意の単語は、pattern内の 1 つの文字に正確にマッピングされます。 - 2つの文字が同じ単語にマップされることはなく、また、2つの単語が同じ文字にマップされることはない。
例
Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
The bijection can be established as:
・ 'a' maps to "dog".
・ 'b' maps to "cat".
Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
制約
1 <= pattern.length <= 300-
patterncontains only lower-case English letters. 1 <= s.length <= 3000-
scontains only lowercase English letters and spaces' '. -
sdoes not contain any leading or trailing spaces. - All the words in
sare separated by a single space.
解答1
文字列がパターンと合致するかを判定する問題です。
パターンの各文字に文字列内の特定の単語が対応します。
各文字(aやb)をキー、sの中の単語をバリューとしたマップ、
sの中の単語をキー、各文字(aやb)をバリューとしたマップ を作成することで、
パターンの合致を比較することが可能です。
コード
func wordPattern(pattern string, s string) bool {
words := strings.Split(s, " ")
ptLen := len(pattern)
wsLen := len(words)
if ptLen != wsLen {
return false
}
charMap := make(map[byte]string)
wordMap := make(map[string]byte)
for i := range ptLen {
ch := pattern[i]
w := words[i]
word, cExist := charMap[ch]
if cExist {
if word != w {
return false
}
}
char, wExist := wordMap[w]
if wExist {
if char != ch {
return false
}
}
charMap[ch] = w
wordMap[w] = ch
}
return true
}
補足
for i := range 数値という書き方は、go1.22 から可能です。
それ以前の場合は、for i := 0; i < 数値; i++という形で記述する必要があります。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(k)
- k = ユニークな文字 or 単語数。制約が 300 以内なので実質定数
解答2
解答1では文字と単語をマッピングしましたが、indexをバリューとしたマップを作成して比較することも可能です。
コード
func wordPattern(pattern string, s string) bool {
words := strings.Split(s, " ")
ptLen := len(pattern)
wsLen := len(words)
if ptLen != wsLen {
return false
}
charMap := make(map[byte]int)
wordMap := make(map[string]int)
for i := range ptLen {
ch := pattern[i]
w := words[i]
// それぞれ直近で出現したインデックスを比較
if charMap[ch] != wordMap[w] {
return false
}
charMap[ch] = i + 1 // 0 と区別するため +1
wordMap[w] = i + 1
}
return true
}
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(k)
- k = ユニークな文字 or 単語数。制約が 300 以内なので実質定数
参考
今回の問題と似ている問題も以下の記事で紹介していますので、参考にしてください。
Discussion