# Question

Formatted question description: https://leetcode.ca/all/291.html

 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.

Examples:

pattern = "abab", str = "redblueredblue" should return true. (a->red, b->blue)
pattern = "aaaa", str = "asdasdasdasd" should return true. (a->asd)
pattern = "aabb", str = "xyzabcxzyabc" should return false.

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



# Algorithm

To use HashMap to establish the mapping between pattern characters and words, you also need to use variables p and r to record the position of the pattern character and word string currently recursed to.

• In the recursive function, if p and r are equal to the length of the pattern string and the word string respectively, it means that the matching has ended successfully at this time, and ture is returned.
• On the contrary, if one is reached and the other is not, it means that the match has failed, and false is returned.
• If the above conditions are not met, take out the pattern character at the current position, and then traverse backward from position r of the word string, taking out one word each time,
• If the pattern character already exists in the HashMap, and the corresponding word and the extracted word are also equal, then call the recursive function again in the next position,
• If it returns true, then return true.
• On the contrary, if the pattern character is not in the HashMap, it depends on whether other pattern characters have been mapped to the word currently taken out.
• If not, create a new mapping and call the recursive function
• Note that if the recursive function returns false, delete this mapping in the HashMap

### Pitfall

Don’t forget below part during DFS.

map.remove(patternChar); // @note: need to remove, since this attempt is failed
inverseMap.remove(tentativeMatchString);


# Code

Java

• import java.util.HashMap;

public class Word_Pattern_II {

public static void main(String[] args) {
Word_Pattern_II out = new Word_Pattern_II();
Solution s = out.new Solution();

System.out.println(s.wordPattern("abab", "redblueredblue"));
System.out.println(s.wordPattern("aaaa", "asdasdasdasd"));
System.out.println(s.wordPattern("aabb", "xyzabcxzyabc"));
System.out.println(s.wordPattern("aaaa", "asdyyyasdyyy")); // false
}

public class Solution {

public boolean wordPattern(String pattern, String str) {

HashMap<Character, String> map = new HashMap<>();
HashMap<String, Character> inverseMap = new HashMap<>();

return dfs(pattern, 0, str, 0, map, inverseMap);
}

// p: pattern length
// r: word length
boolean dfs(String pattern, int pattenIndex, String str, int strIndex, HashMap<Character, String> map, HashMap<String, Character> inverseMap) {

if (pattenIndex == pattern.length() && strIndex == str.length()) {
return true;
}
if (pattenIndex == pattern.length() || strIndex == str.length()) { // didn't hit above if but this one
return false;
}

char patternChar = pattern.charAt(pattenIndex);

for (int i = strIndex; i < str.length(); ++i) {
String tentativeMatchString = str.substring(strIndex, i + 1);

if (map.containsKey(patternChar) && map.get(patternChar).equals(tentativeMatchString) && inverseMap.containsKey(tentativeMatchString) && inverseMap.get(tentativeMatchString).equals(patternChar)) {
if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
return true;
}

} else if (!map.containsKey(patternChar)) {

if (!inverseMap.containsKey(tentativeMatchString)) { // new pattern needed
map.put(patternChar, tentativeMatchString);
inverseMap.put(tentativeMatchString, patternChar);

if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
return true;
}

map.remove(patternChar); // @note: need to remove, since this attempt is failed
inverseMap.remove(tentativeMatchString);
}
}
}
return false;
}
}
}

• // OJ: https://leetcode.com/problems/word-pattern-ii/
// Time: O(PS)
// Space: O(S)
class Solution {
public:
bool wordPatternMatch(string p, string s) {
unordered_map<char, string> m;
unordered_set<string> seen;
function<bool(int,int)> dfs = [&](int i, int j) {
if (i == p.size()) return j == s.size();
if (m.count(p[i])) {
auto t = m[p[i]];
return s.substr(j, t.size()) == t && dfs(i + 1, j + t.size());
} else {
string t;
for (int k = j; k < s.size(); ++k) {
t += s[k];
if (seen.count(t)) continue;
seen.insert(t);
m[p[i]] = t;
if (dfs(i + 1, k + 1)) return true;
seen.erase(t);
m.erase(p[i]);
}
}
return false;
};
return dfs(0, 0);
}
};

• class Solution(object):
def wordPatternMatch(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""

def dfs(p, s, pathp, paths, visited):
if len(p) == len(s) == 0:
return True
if len(p) == 0 or len(p) > len(s):
return False
for i in range(0, len(s)):
pathp.append(p)
paths.append(s[:i + 1])
if len(pathp) == len(paths) and len(set(paths)) == len(set(pathp)) == len(set(zip(paths, pathp))):
if dfs(p[1:], s[i + 1:], pathp, paths, visited):
return True
pathp.pop()
paths.pop()
return False

return dfs(pattern, str, [], [], {})