LeetCode Q290: Word Pattern

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:

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:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution:

	class Solution {
	public:
	bool wordPattern(string pattern, string str) {
	unordered_map<char, string> myMap0;
	unordered_map<string, char> myMap1;
	vector<string> subStrs;
	string _str;
	for(int i=0; i<str.length(); i++){
	if(str[i]==' '&&_str.length()!=0){
	subStrs.push_back(_str);
	_str=string("");
	}
	if(str[i]!=' ')
	_str=_str+string(1, str[i]);
	}
	if(str.length()!=0)
	subStrs.push_back(_str);
	if(pattern.length()!=subStrs.size())
	return false;
	for(int i=0; i<pattern.length(); i++){
	auto it0 = myMap0.find(pattern[i]);
	auto it1 = myMap1.find(subStrs[i]);
	if(it0==myMap0.end()&&it1==myMap1.end()){
	myMap0[pattern[i]]=subStrs[i];
	myMap1[subStrs[i]]=pattern[i];
	}else{
	if(it0!=myMap0.end()&&it1!=myMap1.end())
	if(it0->first==it1->second||it0->second==it1->first)
	continue;
	else
	return false;
	else
	return false;
	}
	}
	return true;
	}
	};

view raw Q290.cpp hosted with ❤ by GitHub