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.
解法：遍历pattern，保存好当前的模式，同时遍历str，也保存下str的模式，二者匹配。
class Solution { public: bool wordPattern(string pattern, string str) { int ps = pattern.size(), ss = str.size(); vector< pair<char, int> > vc; vector< pair<string, int> > vs; int i = 0, j = 0, k = 0; for(; i < ps; ++i) { vector< pair<char, int> >::iterator iter1 = myFind(vc.begin(), vc.end(), pattern[i]); if(iter1 == vc.end()) vc.push_back(make_pair(pattern[i], 1)); else iter1->second += 1;
while(j < ss && str[j] == ‘ ‘) ++j; k = j; while(j < ss && str[j] != ‘ ‘) ++j; if(k == j) return false; string s(str.begin() + k, str.begin() + j); vector< pair<string, int> >::iterator iter2 = myFind(vs.begin(), vs.end(), s); if(iter2 == vs.end()) vs.push_back(make_pair(s, 1)); else iter2->second += 1; if(!sameVec(vc, vs)) return false; } return j == ss ? true : false; } private: bool sameVec(const vector< pair<char, int> >& vc, const vector< pair<string, int> >& vs) { int vcs = vc.size(), vss = vs.size(); if(vcs != vss) return false; for(int i = 0; i < vcs; ++i) if(vc[i].second != vs[i].second) return false; return true; } template<typename T> const typename vector< pair<T, int> >::iterator myFind(const typename vector< pair<T, int> >::iterator beg, const typename vector< pair<T, int> >::iterator end, const T& patt) { typename vector< pair<T, int> >::iterator iter = beg; while(iter != end && iter->first != patt) ++iter; return iter; } };
[LeetCode]48. Word Pattern匹配模式
原文：http://www.cnblogs.com/aprilcheny/p/4925028.html