2 hash tables solution


  • 0
    Y
    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            map <char,string> map1;
            map <string,char> map2;
            vector <string> words;
            istringstream s(str);
            string word;
            while(s>>word){
                    words.push_back(word);
            }
            
            if(words.size()!=pattern.size()) return false;
            
            for(int i=0;i<pattern.size();i++){
                map1.insert(make_pair(pattern[i],words[i]));
                map2.insert(make_pair(words[i],pattern[i]));
            }
            for(int i=0;i<pattern.size();i++){
                if(map1[pattern[i]]!=words[i] || map2[words[i]]!=pattern[i]) return false;
            }
            return true;
                    
        }
    };
    

    Use 2 hash table to establish a one-to-one correspondence between the character and the word. So that we can avoid the situation when we have "abba" and "dog dog dog dog" and it returns the answer "true", which should be "false".
    The words can be separated by space using istringstream.


  • 0
    Y

    Further more, if we only want to use one hash table, we can just record the numbers of unique characters and words. If one hash table is valid and those two number are equal, we can say that it should return a "true".


Log in to reply
 

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