Given a pattern and a string str, find if str follows the same pattern.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

 

Notes:

1. Both pattern and str contains only lowercase alphabetical letters.
2. Both pattern and str do not have leading or trailing spaces.
3. Each word in str is separated by a single space.
4. Each letter in pattern must map to a word with length that is at least 1.

 

Credits:

Special thanks to  for adding this problem and creating all test cases.

 

1 class Solution { 2 public: 3     bool wordPattern(string pattern, string str) { 4         vector
     
       dic; 5         istringstream sin(str); 6         string tmp; 7         while (sin >> tmp) dic.push_back(tmp); 8         if (dic.size() != pattern.size()) return false; 9         unordered_map
      
        mp1;10         unordered_map
       
         mp2;11         for (int i = 0; i < pattern.size(); ++i) {12             if (mp1.find(pattern[i]) == mp1.end()) {13                 mp1[pattern[i]] = dic[i];14             } else if (mp1[pattern[i]] != dic[i]) {15                 return false;16             }17             if (mp2.find(dic[i]) == mp2.end()) {18                 mp2[dic[i]] = pattern[i];19             } else if (mp2[dic[i]] != pattern[i]) {20                 return false;21             }22         }23         return true;24     }25 };