290. Word Pattern

Easy

Description

給定 pattern 字串和 string s，判斷 s 是否遵循相同的 pattern。「遵循」意味著 pattern 中的字母和 s 中的單字之間存在雙射（一對一映射）。

Example:

Input: pattern = “abba”, s = “dog cat cat dog” Output: true

Intuition#

核心思路：與 LC 205 (Isomorphic Strings) 相同——需要建立雙向映射，確保 pattern 字母和單字之間是一對一的。

先將 s 按空格分割成單字陣列
如果單字數量與 pattern 長度不同，直接回傳 false
用兩個 Map 維護雙向映射

Approaches#

1: 單向映射（不完整）#

概念: 只維護 pattern → word 的映射，會遺漏「多對一」的情況
時間複雜度: O(n) - n 為 pattern 長度
空間複雜度: 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: 雙向映射#

概念: 用兩個 HashMap 分別維護 char → word 和 word → char 的映射
時間複雜度: O(n)
空間複雜度: 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 同一模式
關鍵技巧: 單向映射不夠，必須雙向檢查；先比較長度是很好的提前剪枝