leetcode筆記：Word Pattern

leetcode筆記：Word Pattern

一. 題目描述

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

二. 題目分析

題目的大意是，給出一組模式（pattern）和一個字符串（str），判斷字符串是否與模式相匹配，並給出了幾個例子。

題目提到，模式pattern僅由小寫字母構成，而字符串str中每個單詞均被單個空格字符隔開，且字符串中每個單詞都由小寫字母構成（這種設定可以少考慮很多邊界條件）；模式pattern和字符串str的前後都不包含多余的空格；且模式pattern中的每個字母必須匹配一個字符串str中長度至少為1的單詞。

容易想到的是，使用Map來解決這個問題。

於是乎，定義一個map，每遇到一個新的模式，以模式為key，將對應的單詞存入map；遇到map裡已有的模式，檢查當前str的單詞是否與map記載模式所對應的value值相同，只要出現不同，直接返回false。

這種判斷方法可以解決：pattern = "abba", str = "dog cat cat fish"這種情況。

但是，只使用一個map無法判斷這種情況：pattern = "abba", str = "dog dog dog dog"，一開始a作為一個新模式，被存入map，到了第二次迭代，b作為一個新模式，也被存入map，dog被分配到兩個不同的模式，顯然這是不對的。

為了解決這個問題，需要兩個map。另一個map2用於記載單詞與模式的對應關系。

總的來說，map用於記載模式到單詞的對應關系，但可能出現多個模式對應到同個單詞的情形。

而map2用於記載單詞到模式的對應關系，在判斷中同時加入對兩個map的判斷，才可以分辨所有情況。

三. 示例代碼

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map map; // 作用是防止出現單詞不同但模式相同的情況
        unordered_map map2; // 作用是防止出現模式不同但單詞同名的情況
        vector vec; // 存放逐個單詞
        // 以下操作分割str為多個單詞
        for (int i = 0, j = 0; i < str.size(); ++i)
        {
            if (i == str.size() - 1)
            {
                string temp = str.substr(j, i - j + 1);
                vec.push_back(temp);
            }
            if (str[i] == ' ')
            {
                string temp = str.substr(j, i - j);
                vec.push_back(temp);
                j = i + 1;
            }
        }

        if (pattern.size() != vec.size()) return false;

        for (int i = 0; i < pattern.size(); ++i)
        {
            // 當前模式未出現，且對應的單詞也未出現，才將鍵值對存入表
            if (map.find(pattern[i]) == map.end() && map2.find(vec[i]) == map2.end())
            {
                map.insert(make_pair(pattern[i], vec[i]));
                map2.insert(make_pair(vec[i], pattern[i]));
            }
            else if (map[pattern[i]] != vec[i]) 
                return false;
        }

        return true;
    }
};

四. 小結

思路簡單的一道題，但實現起來還是要花點時間，而且需要注意一些細節問題。