LeetCode Q291: Word Pattern II (hard)

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 substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

Solution:

Use DFS with recursion. The difficulty is to distinguish each situation during search.

	class Solution {
	public:
	bool helper(string pat, string str, int patLoc, int strLoc,
	unordered_map<char, string>& map0,
	unordered_map<string, char>& map1){
	if(patLoc==pat.length()&&strLoc==str.length())
	return true;
	bool res=false;
	char patChar = pat[patLoc];
	for(int j=1; j<=str.length()-strLoc; j++){
	string subStr = str.substr(strLoc, j);
	auto it0 = map0.find(patChar);
	auto it1 = map1.find(subStr);
	if(it0==map0.end()&&it1==map1.end()){
	map0[patChar]=subStr;
	map1[subStr]=patChar;
	res = helper(pat, str, patLoc+1, strLoc+j, map0, map1);
	if(res)
	return true;
	else{
	map0.erase(patChar);
	map1.erase(subStr);
	}
	continue;
	}
	if(it0!=map0.end()&&it1!=map1.end()){
	if(it0->first==it1->second&&it0->second==it1->first){
	res = helper(pat, str, patLoc+1, strLoc+j, map0, map1);
	if(res)
	return true;
	else
	return false;
	}
	}
	else{
	if(it0==map0.end()||it1==map1.end())
	continue;
	if(it0!=map0.end()&&subStr.length()>(it0->second).length())
	return false;
	continue;
	}
	}
	return false;
	}
	bool wordPatternMatch(string pattern, string str) {
	unordered_map<char, string> map0;
	unordered_map<string, char> map1;
	bool res = helper(pattern, str, 0, 0, map0, map1);
	return res;
	}
	};

view raw Q291.cpp hosted with ❤ by GitHub