Clean C++ Solution with explanation 0ms


  • 0
    S
    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            unordered_map<char, string> strMap;
            vector<string> strList = make_strList(str);
            if ( strList.size() != pattern.size() ) return false;
            unordered_set<string> visited;
            for ( int i = 0; i < pattern.size(); i++ ) {
                if ( strMap.find(pattern[i]) == strMap.end() ) {
                    if ( visited.find(strList[i]) != visited.end() ) return false;
                    else {
                        strMap[pattern[i]] = strList[i];
                        visited.insert(strList[i]);
                    }
                }
                else {
                    if ( strMap[pattern[i]] != strList[i] ) return false;
                }
            }
            return true;
        }
    private:
        vector<string> make_strList(string str) {
            vector<string> ret;
            string word;
            for ( int i = 0; i < str.length(); i++ ) {
                if ( str[i] == ' ') {
                    ret.push_back(word);
                    word.clear();
                } else
                    word.push_back(str[i]);
            }
            ret.push_back(word);
            return ret;
        }
    };
    

    Explanation:
    We can see the pattern element as key and the words in the string is a value. We make the key and value pattern, return false if we find a value didn't match the key.
    Making a word list storing the words. And keep making the key and word pattern, store them in a hash table. We also need a set to track the value we have seen before. Therefore, when the new key appears, it should match with a new word. (If the word appeared before, return false) If the old key show up, we check if the value is the same as old key's value. Return false if it is not.


Log in to reply
 

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