题目描述:（链接）
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
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:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
解题思路：
找到字符和字符串之间的映射关系就行了，用两个哈希表分别存放<字符，字符串>和<字符串, 字符>的映射关系，前提需要分解字符串(split函数)。
1 class Solution { 2 public: 3 bool wordPattern(string pattern, string str) { 4 unordered_map<char, string> cache1; 5 unordered_map<string, char> cache2; 6 7 vector<string> splitStrs = split(str, ‘ ‘); 8 9 if (splitStrs.size() != pattern.size()) { 10 return false; 11 } 12 13 for (size_t i = 0; i < pattern.size(); ++i) { 14 if (cache1.find(pattern[i]) == cache1.end() && cache2.find(splitStrs[i]) == cache2.end()) { 15 cache1[pattern[i]] = splitStrs[i]; 16 cache2[splitStrs[i]] = pattern[i]; 17 } else if (cache1.find(pattern[i]) != cache1.end() && cache2.find(splitStrs[i]) != cache2.end()){ 18 if (cache1[pattern[i]] != splitStrs[i] && cache2[splitStrs[i]] != pattern[i]) { 19 return false; 20 } 21 } else { 22 return false; 23 } 24 } 25 26 return true; 27 } 28 private: 29 vector<string> split(const string& src, char sep) { 30 vector<string> result; 31 size_t lastIndex = 0; 32 size_t index = 0; 33 while ((index = src.find(sep, lastIndex)) != string::npos) { 34 result.push_back(src.substr(lastIndex, index - lastIndex)); 35 lastIndex = index + 1; 36 } 37 38 string lastStr = src.substr(lastIndex); 39 if (!lastStr.empty()) { 40 result.push_back(lastStr); 41 } 42 43 return result; 44 } 45 };
原文：http://www.cnblogs.com/skycore/p/4869150.html