Given a pattern and a string str, find if str follows the same pattern.
Examples:
"abba", str = "dog cat cat dog" should return true."abba", str = "dog cat cat fish" should return false."aaaa", str = "dog cat cat dog" should return false."abba", str = "dog dog dog dog" should return false.
Notes:
pattern and str contains only lowercase alphabetical letters.pattern and str do not have leading or trailing spaces.str is separated by a single space.pattern must map to a word with length that is at least 1.
Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.
1 class Solution { 2 public: 3 bool wordPattern(string pattern, string str) { 4 vector<string> 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<char, string> mp1; 10 unordered_map<string, char> 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 };
原文：http://www.cnblogs.com/easonliu/p/4856850.html