Problem

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 non-empty 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.

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Notes

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

This is a follow up of Word Pattern 1.

Solution

Method 1 - Backtracking with 2 Hashmaps 🏆

We can use 2 hashmaps:

  • Use a HashMap to map characters in the pattern to substrings in s.
  • Use another HashMap to ensure the mapping is bijective.
  • Use recursion to explore mappings until the entire pattern and string have been matched or a mismatch is detected.

We will have following cases in backtracking:

  • If both the pattern and string are fully matched, return true.
  • If either the pattern or the string is fully matched but the other is not, return false.
  • Ensure proper backtracking by removing the mapping when a mismatch occurs.

For edge case, don’t forget below part during DFS.

1
2

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

Code

 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

public class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        Map<String, Character> inverseMap = new HashMap<>();
        return dfs(pattern, s, 0, 0, map, inverseMap);
    }

    private boolean dfs(String pat, String str, int patIdx, int strIdx, Map<Character, String> map, Map<String, Character> inverseMap) {
        if (patIdx == pat.length() && strIdx == str.length()) {
            return true;
        }
        if (patIdx == pat.length() || strIdx == str.length()) {
            return false;
        }

        char patternChar = pat.charAt(patIdx);
        for (int i = strIdx; i < str.length(); ++i) {
            String tentativeMatchString = str.substring(strIdx, i + 1);
            if (map.containsKey(patternChar)) {
                if (map.get(patternChar).equals(tentativeMatchString) && dfs(pat, str, patIdx + 1, i + 1, map, inverseMap)) {
                    return true;
                }
            } else if (!inverseMap.containsKey(tentativeMatchString)) {
                map.put(patternChar, tentativeMatchString);
                inverseMap.put(tentativeMatchString, patternChar);
                if (dfs(pat, str, patIdx + 1, i + 1, map, inverseMap)) {
                    return true;
                }
                map.remove(patternChar);
                inverseMap.remove(tentativeMatchString);
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def dfs(pat: str, s: str, patIdx: int, strIdx: int, map: Dict[chr, str], inverseMap: Dict[str, chr]) -> bool:
            if patIdx == len(pat) and strIdx == len(s):
                return True
            if patIdx == len(pat) or strIdx == len(s):
                return False

            patternChar = pat[patIdx]
            for i in range(strIdx, len(s)):
                tentativeMatchString = s[strIdx:i + 1]
                if patternChar in map:
                    if map[patternChar] == tentativeMatchString and dfs(pat, s, patIdx + 1, i + 1, map, inverseMap):
                        return True
                elif tentativeMatchString not in inverseMap:
                    map[patternChar] = tentativeMatchString
                    inverseMap[tentativeMatchString] = patternChar
                    if dfs(pat, s, patIdx + 1, i + 1, map, inverseMap):
                        return True
                    del map[patternChar]
                    del inverseMap[tentativeMatchString]
            return False

        return dfs(pattern, s, 0, 0, {}, {})

Complexity

  • ⏰ Time complexity: O(n^m) where n is the length of the string and m is the length of the pattern.
  • 🧺 Space complexity: O(m + n) for storing the mappings and recursive call stack.