給定 pattern 字串和 string
s，判斷s是否遵循相同的 pattern。「遵循」意味著 pattern 中的字母和s中的單字之間存在雙射（一對一映射）。
Example:
Input: pattern = “abba”, s = “dog cat cat dog” Output: true
Intuition
TIP
核心思路：與 LC 205 (Isomorphic Strings) 相同——需要建立雙向映射，確保 pattern 字母和單字之間是一對一的。
- 先將
s按空格分割成單字陣列 - 如果單字數量與 pattern 長度不同，直接回傳 false
- 用兩個 Map 維護雙向映射
Approaches
1. One-Way Mapping (incomplete) — O(n) / O(n)
- Idea: 只維護 pattern → word 的映射，會遺漏「多對一」的情況
- Time:
O(n)- n 為 pattern 長度 - Space:
O(n)- HashMap
class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
val words = s.split(" ")
if (pattern.length != words.size) return false
val map = HashMap<Char, String>()
val used = HashSet<String>()
for (i in pattern.indices) {
val c = pattern[i]
val w = words[i]
if (map.containsKey(c)) {
if (map[c] != w) return false
} else {
if (w in used) return false
map[c] = w
used.add(w)
}
}
return true
}
}⭐ 2. Bidirectional Mapping — O(n) / O(n)
- Idea: 用兩個 HashMap 分別維護
char → word和word → char的映射 - Time:
O(n) - Space:
O(n)
class Solution {
fun wordPattern(pattern: String, s: String): Boolean {
val words = s.split(" ")
if (pattern.length != words.size) return false
val charToWord = HashMap<Char, String>()
val wordToChar = HashMap<String, Char>()
for (i in pattern.indices) {
val c = pattern[i]
val w = words[i]
if (charToWord.containsKey(c) && charToWord[c] != w) return false
if (wordToChar.containsKey(w) && wordToChar[w] != c) return false
charToWord[c] = w
wordToChar[w] = c
}
return true
}
}🔑 Takeaways
- Pattern: 雙向映射驗證，與 LC 205 Isomorphic Strings 同一模式
- Key trick: 單向映射不夠，必須雙向檢查；先比較長度是很好的提前剪枝