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);
                vis.add(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
                    vis.add(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)
}

291 - Word Pattern II

Question

Algorithm

Pitfall

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Pitfall

Code

All Problems

All Solutions