290. Word Pattern
Easy
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
.Example 1:
Input: pattern = "abba", s = "dog cat cat dog"
Output:
true
Example 2:
Input: pattern = "abba", s = "dog cat cat fish"
Output:
false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog"
Output:
false
Constraints:
1 <= pattern.length <= 300
pattern
contains only lower-case English letters.1 <= s.length <= 3000
s
contains only lowercase English letters and spaces' '
.s
does not contain any leading or trailing spaces.- All the words in
s
are separated by a single space.
時間複雜度 O(n)
func wordPattern(pattern string, s string) bool {
words := strings.Fields(s)
if len(words)!=len(pattern) { return false }
m := make(map[uint8]string)
m2 := make(map[string]uint8)
for i:=0; i<len(words); i++ {
if val, ok := m[pattern[i]]; ok {
if val!=words[i] {
return false
}
} else {
m[pattern[i]] = words[i]
}
if val, ok := m2[words[i]]; ok {
if val != pattern[i] {
return false
}
} else {
m2[words[i]] = pattern[i]
}
}
return true
}
Last modified 7mo ago