題目描述

給定模式串 pattern（僅小寫字母）和字符串 str（單詞以單空格分隔），判斷 str 是否遵循 pattern 的雙射關係：每個字母唯一對應一個非空單詞，且不同字母對應不同單詞。

示例：

• abba, "dog cat cat dog" → true
• abba, "dog cat cat fish" → false
• aaaa, "dog cat cat dog" → false
• abba, "dog dog dog dog" → false

核心算法：雙向映射驗證

維護兩個結構：

• char → string 映射（unordered_map）
• string → bool 已用單詞集合（unordered_set）

遍歷模式字符與單詞：

1. 若字符未映射：
   • 單詞已被用 → false
   • 建立映射，標記單詞已用
2. 若字符已映射：檢查映射值是否等於當前單詞，不等 → false

長度不匹配直接 false。

完整代碼

// C++ Runtime: 0 ms
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector<string> words;
        istringstream iss(str);
        string w;
        while (iss >> w) words.push_back(w);
        if (words.size() != pattern.size()) return false;

        unordered_map<char, string> map;
        unordered_set<string> used;
        for (int i = 0; i < pattern.size(); i++) {
            char c = pattern[i];
            if (!map.count(c)) {
                if (used.count(words[i])) return false;
                map[c] = words[i];
                used.insert(words[i]);
            } else if (map[c] != words[i]) {
                return false;
            }
        }
        return true;
    }
};

// Java Runtime: 3 ms
public class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (pattern.length() != words.length) return false;
        Map<Character, String> map = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map.containsKey(c)) {
                if (map.containsValue(words[i])) return false;
                map.put(c, words[i]);
            } else if (!map.get(c).equals(words[i])) {
                return false;
            }
        }
        return true;
    }
}

複雜度分析

• 時間：O(n) 平均（n = pattern.length()，Hash 操作 O(1) 平均）
• 空間：O(k) k 為不同字符數（≤26）

關鍵細節

• C++ 用 istringstream 分割字符串，Java 用 split(" ")
• 雙向檢查確保單射：map 保證字符→單詞唯一，used 保證單詞→字符唯一
• Java map.containsValue 是 O(n)，但 k≤26 可忽略；大規模時應維護反向 Map<String, Character>