LeetCode [291] Word Pattern II

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.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: bool wordPatternMatch(string pattern, string str) { unordered_map<char, string> hash1; unordered_map<string, char> hash2; return bt(pattern, str, 0, 0, pattern.size(), str.size(), hash1, hash2); } bool bt(string &pattern, string &str, int p, int s, int np, int ns, unordered_map<char, string> &hash1, unordered_map<string, char> &hash2){ if(p==np && s==ns){ return true; }else if(p<np && s<ns){ char c = pattern[p]; if(hash1.count(c)){ int len = hash1[c].size(); if(s+len<=ns && str.substr(s, len)==hash1[c] && bt(pattern, str, p+1, s+len, np, ns, hash1, hash2)){ return true; }else{ return false; } }else{ for(int i=s; i<ns; ++i){ string ss = str.substr(s, i-s+1); if(hash2.count(ss)==0){ hash1[c] = ss; hash2[ss] = c; if(bt(pattern, str, p+1, i+1, np, ns, hash1, hash2)) return true; hash2.erase(ss); hash1.erase(c); } } } } return false; } };