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)

results matching ""

    No results matching ""