題目描述:給定模式字串 pattern 和以空格分隔的字串 s,判斷 s 是否完全遵循 pattern(即字元與單詞之間存在雙射對應)。
解題思路:將 s 切割成單詞陣列,長度必須與 pattern 相同。維護兩個雜湊表:char→word 和 word→char。對每個位置,若映射已存在則驗證一致性;若不存在則建立新映射。雙向映射確保是真正的雙射(bijection)而非單純的單射。
時間複雜度:O(n) — n 為 s 的長度,切割與遍歷各為線性。
空間複雜度:O(k) — k 為不重複字元或單詞的數量,最多 26 個字元映射。
1. Split s into words array 2. If len(pattern) != len(words), return false 3. Initialize maps c2w (char→word) and w2c (word→char) 4. For each index i: a. If c2w[pattern[i]] exists and != words[i]: return false b. If w2c[words[i]] exists and != pattern[i]: return false c. Set c2w[pattern[i]] = words[i], w2c[words[i]] = pattern[i] 5. Return true
索引標準化 O(n):對 pattern 和 words 各自建立「首次出現索引」序列,若兩序列相同則模式一致 — 等價但不直觀。
單一映射 O(n):只做 char→word 單向映射會漏掉多對一的情況(如 'a'→'dog', 'b'→'dog'),必須雙向映射才完整。