# Question

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

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"


Example 3:

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


Constraints:

• 1 <= pattern.length, s.length <= 20
• pattern and s consist of only lowercase English 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

• 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;
}
}
}

############

class Solution {
private Set<String> vis;
private Map<Character, String> d;
private String p;
private String s;
private int m;
private int n;

public boolean wordPatternMatch(String pattern, String s) {
vis = new HashSet<>();
d = new HashMap<>();
this.p = pattern;
this.s = s;
m = p.length();
n = s.length();
return dfs(0, 0);
}

private boolean dfs(int i, int j) {
if (i == m && j == n) {
return true;
}
if (i == m || j == n || m - i > n - j) {
return false;
}
char c = p.charAt(i);
for (int k = j + 1; k <= n; ++k) {
String t = s.substring(j, k);
if (d.getOrDefault(c, "").equals(t)) {
if (dfs(i + 1, k)) {
return true;
}
}
if (!d.containsKey(c) && !vis.contains(t)) {
d.put(c, t);
if (dfs(i + 1, k)) {
return true;
}
vis.remove(t);
d.remove(c);
}
}
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, s):
"""
:type pattern: str
:type s: str
:rtype: bool
"""

# pathp: path for pattern
# paths: path for matched strings
def dfs(p, s, pathp, paths):
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[0])
paths.append(s[:i + 1])
# same as in Word-Pattern-I, for checking if valid
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):
return True
pathp.pop()
paths.pop()
return False

return dfs(pattern, s, [], [])

############

'''
>>> d = {}
>>> d.get('a')
>>>
>>> r = d.get('a')
>>> r
>>>
>>> if not r:
...     print('aa')
aa
'''
class Solution:
def wordPatternMatch(self, pattern: str, s: str) -> bool:
def dfs(i, j):
if i == m and j == n:
return True
if i == m or j == n or n - j < m - i:
return False
for k in range(j, n):
t = s[j : k + 1]
if d.get(pattern[i]) == t: # if not in dict, return empty
if dfs(i + 1, k + 1):
return True
if pattern[i] not in d and t not in vis:
d[pattern[i]] = t
if dfs(i + 1, k + 1):
return True
d.pop(pattern[i])
vis.remove(t)
return False

m, n = len(pattern), len(s)
d = {}
vis = set()
return dfs(0, 0)


• func wordPatternMatch(pattern string, s string) bool {
m, n := len(pattern), len(s)
vis := map[string]bool{}
d := map[byte]string{}
var dfs func(i, j int) bool
dfs = func(i, j int) bool {
if i == m && j == n {
return true
}
if i == m || j == n || m-i > n-j {
return false
}
c := pattern[i]
for k := j + 1; k <= n; k++ {
t := s[j:k]
if v, ok := d[c]; ok && v == t {
if dfs(i+1, k) {
return true
}
}
if _, ok := d[c]; !ok && !vis[t] {
d[c] = t
vis[t] = true
if dfs(i+1, k) {
return true
}
delete(d, c)
vis[t] = false
}
}
return false
}
return dfs(0, 0)
}