LeetCode 290 Word Pattern 單詞模式：雙向映射與字串分割解法

題目描述

給定一個模式字串 pattern（僅含小寫字母）和一個字串 str（單詞以單一空格分隔），判斷 str 是否遵循相同模式。這裡的「遵循」意味著雙向一一對應：pattern 中的每個字元唯一對應 str 中的一個非空單詞，反之亦然。

範例

題目分析

核心難點在於建立 雙向映射：

• 單向映射（char → word）無法檢測「不同字元對應相同單詞」的情況（如 abba vs dog dog dog dog）。
• 需同時維護 map 和 map，確保一一對應。

演算法步驟

1. 將 str 按空格分割為單詞陣列 words。
2. 若 pattern.length() != words.size()，直接返回 false。
3. 遍歷 pattern 與 words：
   • 若雙向映射中均無對應，建立新映射。
   • 若任一映射衝突，返回 false。
4. 遍歷結束返回 true。

C++ 參考實作

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map char2word;
        unordered_map word2char;
        vector words;
        
        // 分割字串
        for (int i = 0, j = 0; i <= str.size(); ++i) {
            if (i == str.size() || str[i] == ' ') {
                words.push_back(str.substr(j, i - j));
                j = i + 1;
            }
        }
        
        if (pattern.size() != words.size()) return false;
        
        for (int i = 0; i < pattern.size(); ++i) {
            char c = pattern[i];
            const string& w = words[i];
            
            if (!char2word.count(c) && !word2char.count(w)) {
                char2word[c] = w;
                word2char[w] = c;
            } else if (char2word[c] != w || word2char[w] != c) {
                return false;
            }
        }
        return true;
    }
};

複雜度分析

• 時間複雜度：O(n)，n 為字串長度，分割與遍歷皆為線性。
• 空間複雜度：O(m)，m 為不同字元/單詞數量，雜湊表儲存映射。

關鍵點總結

1. 雙向映射是解決一一對應問題的標準技巧。
2. 字串分割可用 stringstream、getline 或手動雙指標。
3. 注意邊界：空字串、尾部無空格、單詞數量不匹配。