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.
题目的大致意思是：给两个字符串，其中一个表示轨迹，检查第二个字符串是否符合第一个轨迹而存在，如果两者轨迹相同返回true，不同则返回false。 其中注意:pattern="aaaa",str="aa aa aa aa aa aa"两者轨迹并不相同
class Solution { public: bool wordPattern(string pattern, string str) { auto beg = begin(str), en = end(str); string::iterator mid=beg; map<char, string> ma; for (unsigned i = 0;i < pattern.size();++i) { for (;mid != en && ((*mid) != ‘ ‘);++mid); if(ma.find(pattern[i])==ma.end()) ma[pattern[i]] = string(beg, mid); if (ma.find(pattern[i]) != ma.end() && ma[pattern[i]] != string(beg, mid)) return false; if(mid!=en) beg = ++mid; } map<string, char> test; for (auto e : ma) test[e.second] = e.first; if (ma.size( )!= test.size()||mid!=en) return false; return true; } };
原文：http://www.cnblogs.com/csudanli/p/5313108.html