C++ solution using two hash map with O(n) Time complexity


  • 0
    Y
    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            if(!pattern.size() && !str.size())
                return true;
            int wrd_cnt = 0;
            int idx = 0;
            for(int i = 0; i < pattern.size(); ++ i){
                char kv = pattern[i];
                string wkv = "";
                while(str[idx] == ' ' && idx < str.size())
                    ++ idx;
                while(str[idx] != ' ' && idx < str.size()){
                    wkv += str[idx];
                    ++ idx;
                }
                if(ptn_wrd.find(kv) != ptn_wrd.end()){
                    if(ptn_wrd[kv] != wkv)
                        return false;
                }else{
                    ptn_wrd[kv] = wkv;
                    if(wrd_ptn.find(wkv) != wrd_ptn.end()){
                        if(wrd_ptn[wkv] != kv)
                            return false;
                    }else{
                        wrd_ptn[wkv] = kv;
                    }
                }
                ++ wrd_cnt;
                if(idx >= str.size())
                    break;
            }
            if(wrd_cnt != pattern.size() || (wrd_cnt == pattern.size() && idx < str.size()))
                return false;
            return true;
        }
    private:
    unordered_map<char,string> ptn_wrd;
    unordered_map<string, char> wrd_ptn;
    };

  • 1
    P

    Error when debug: string out of range!
    this line " while(str[idx] == ' ' && idx < str.size())"
    should be
    " while( idx < str.size() && str[idx] == ' ' )"


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.