290

這題比較偏向是把我們自己腦袋裡的演算法實作出來。以 290. Word Pattern 裡面舉的例子來說，我們可以先看看自己是怎麼做到這種 word pattern 的辨識，把演算法釐清之後，再寫成程式碼。

首先，看題目中舉的第一個例子: pattern = "abba", str = "dog cat cat dog" should return true.，我們在做的事情其實是

1. 先看 pattern 的第一個 a ，然後在心中把 a 對應到 str 的 dog，並把這個對應關係存起來
2. 看 pattern 的第二個字 b，先看 b 有沒有出現過。如果有的話，那就要驗證 str 的 cat 是不是跟之前儲存的對應關係一致；如果沒有的話，那就要先檢查 cat 有沒有被存過，有的話就要直接回傳錯誤，沒有的話，才儲存 b 對應到 cat 的這個對應關係。
3. 依序這樣做下去(跑完 pattern 裡的每一個單字)，如果都沒有遇到跟儲存的對應關係衝突的，那就表示正確；但只要一有衝突，就錯誤。

接下來就只剩把我們自己心中的做法寫成 code，這邊比較特別的就是，對應關係可以使用 C++ 的 map 來儲存,另外要記得把 str 的每一個部分先 tokenize。

寫成 code 就是: (為了判斷 token 裡的值有沒有被存過，我弄了另外一個方向的 map，導致 Mapping & Finding Conflicts 部分寫得有點醜，之後有機會再來優化，可以參考這一篇)

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        //Tokenization
        vector<string> token;
        char * split;
        char * cstr = new char [str.length()+1];
        std::strcpy (cstr, str.c_str());
        split = strtok(cstr," ");
        while(split != NULL)
        {
            token.push_back(split);
            split = strtok(NULL, " ");
        }

        //Check for special case, e.g. pattern="jquery", str="jquery" 
        if(token.size() != pattern.size())
            return false;

        //Mapping and finding conflicts
        map<char, string> mapStr;
        map<string, char> mapInv;

        for(int i=0; i<pattern.size(); i++)
        {
            if(mapStr.find( pattern[i] ) == mapStr.end())
            {
                //if token[i] exists in mapInv, then there is a conflict
                if(mapInv.find( token[i] ) != mapInv.end())
                    return false;
                else
                {
                    mapStr[pattern[i]] = token[i];
                    mapInv[token[i]] = pattern[i];
                }
            }
            else
            {
                if(token[i] != mapStr[pattern[i]])
                    return false;
            }
        }

        return true;
    }
};

我一開始寫的版本沒有做 boundary case 的檢查，會掛在 pattern="jquery",str="jquery"，這種case上面，所以 tokenization 之後有額外加上一點點檢查。 (之後如果更有時間，確實是應該養成考慮 boundary case 的習慣，這樣寫出來的 code 更 robust)