題目敘述
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 <= 300pattern contains only lower-case English letters.1 <= s.length <= 3000s 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.
題目翻譯
這題會提供兩個變數，第一個變數 pattern 會給你一個規則，第二個變數 s 則是給你一個字串(字串中的字詞都用' '來隔開)。題目就是要用 pattern 去判斷是否 s 是否有符合規範。
解法解析
這題可以用一個或兩個 Hash Map 來去解。
- Time complexity : O(N)，N 是指
pattern 的長度
- Space complexity : O(M)，M 是指
pattern 中唯一字數的數量
我這邊的範例是採用了單一 Hash Map 的方式來去解，但其他相差不多。
第一步先篩選掉最好判斷的長度問題。兩個變數的字詞數不同和唯一字詞數不同的都先去掉。
第二步就是開始去判斷規範了，使用一個 dict 來記錄判斷過的規則。這邊看要遍歷 pattern 或是拆分後的 s 都可以。一旦發現已經儲存的規範，但是跟應該對應的值不同的話就判斷失敗。
最後當整個都遍歷後，就代表 s 是符合 pattern 規範的，所以回傳 True
程式範例
Python
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
map_index = {}
words = s.split()
if len(pattern) != len(words):
return False
if len(set(pattern)) != len(set(words)):
return False
for i in range(len(words)):
c = pattern[i]
w = words[i]
if c in map_index and map_index[c] != w:
return False
map_index[c] = w
return True
JavaScript
var wordPattern = function (pattern, s) {
const words = s.split(' ');
const map = new Map();
if (words.length !== pattern.length) return false;
if (new Set(words).size !== new Set(pattern).size) return false;
for (let i = 0; i < pattern.length; i++) {
if (map.has(pattern[i]) && map.get(pattern[i]) !== words[i])
return false;
map.set(pattern[i], words[i]);
}
return true;
};
Go
func wordPattern(pattern string, s string) bool {
pp := strings.Split(pattern, "")
sp := strings.Split(s, " ")
if len(pp) != len(sp) {
return false
}
mp := map[string]string{}
ms := map[string]string{}
for i, c := range pp {
msp, okp := mp[c]
cs, oks := ms[sp[i]]
if okp != oks || oks && (c != cs || msp != sp[i]) {
return false
}
mp[c] = sp[i]
ms[sp[i]] = c
}
return true
}
Swift
class Solution {
func wordPattern(_ pattern: String, _ s: String) -> Bool {
let chars = [Character](pattern)
let words = s.components(separatedBy: " ")
if chars.count != words.count { return false }
var letterToWordHash = [String: String]()
var wordToLetterHash = [String: String]()
for (index, letter) in letters.enumerated() {
let word = words[index]
if let existingWordHash = letterToWordHash[letter], word != existingWordHash { return false }
if let existingLetterHash = wordToLetterHash[word], letter != existingLetterHash { return false }
letterToWordHash[letter] = word
wordToLetterHash[word] = letter
}
return true
}
}
Kotlin
class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
val parseString = s.split(" ")
if (pattern.length != parseString.size) return false
val patternMap = hashMapOf<Char, Int>()
val parseStringMap = hashMapOf<String, Int>()
for (index in 0..pattern.lastIndex) {
if (patternMap[pattern[index]] != parseStringMap[parseString[index]]) return false
patternMap[pattern[index]] = index
parseStringMap[parseString[index]] = index
}
return true
}
}