Leetcode 291. Word Pattern II
Problem
We are given a pattern and a string and the goal is to determine if the string follows the same pattern as the pattern string. By "follows the same pattern", we mean that there is a bijection between a letter in the pattern and a non-empty substring in the string.
In simple terms, each unique character in pattern can be mapped to a unique substring of str, and this map must be consistent throughout the length of both pattern and str. For example, if pattern = "abab" and str = "redblueredblue", then we have a (unique) map 'a' -> "red", 'b' -> "blue" and this map is consistent with the pattern and the string.
Let's break it down using example 1: pattern = "abab", str = "redblueredblue"
- We start with the first character in pattern 'a'. We map 'a' to the first substring in str "red".
- We then move to the next character in pattern 'b'. We map 'b' to the next substring in str "blue".
- We move again to the third character in pattern 'a'. We check if the next substring in str matches the substring we have mapped to 'a' already. In this case, it does ("red").
- We repeat this process for the rest of the characters and substrings. If at any point there is not a match, we return False. If we get through the entire pattern and str with consistent matches, we return True.
Approach
This problem is a classic problem that can be solved using Backtracking and Hashing.
- We use a hash map to store the mappings from characters to strings.
- We also store the strings that have already been mapped in a set.
- We try different mappings and if we hit a dead-end (i.e., the mappings are not consistent), we backtrack and try other mappings.
Let's implement this in Python:
Python
1 2python 3class Solution: 4 def wordPatternMatch(self, pattern: str, s: str) -> bool: 5 def isMatch(pattern, i, s, j, char_to_str_map, str_set): 6 if i == len(pattern) and j == len(s): return True 7 if i == len(pattern) or j == len(s): return False 8 9 # pattern[i] has already been mapped to a substring 10 if pattern[i] in char_to_str_map: 11 t = char_to_str_map[pattern[i]] 12 if not s.startswith(t, j): return False 13 return isMatch(pattern, i+1, s, j+len(t), char_to_str_map, str_set) 14 15 for k in range(j, len(s)): 16 t = s[j: k + 1] 17 if t in str_set: continue 18 str_set.add(t) 19 char_to_str_map[pattern[i]] = t 20 if isMatch(pattern, i+1, s, k+1, char_to_str_map, str_set): return True 21 str_set.remove(t) 22 del char_to_str_map[pattern[i]] 23 24 return False 25 26 return isMatch(pattern, 0, s, 0, {}, set())
In this Python solution, we implement the isMatch
function which does the Backtracking for us. This function is:
- Checking if we have reached the end of the
pattern
ands
(base case). - If we have already mapped the current pattern character (
pattern[i]
) to a substring, we are checking this mapping with the current substring ins
. If they do not match, we returnFalse
, else we callisMatch
recursively on the next pattern character and next substring. - If we haven't mapped the current pattern character, we are trying to map it to all possible substrings in
s
that start atj
. We continue to do this until we find a match or exhaust all possibilities, in which case we returnFalse
.## Javascript
We can apply the same approach for the Javascript solution of the problem:
1
2javascript
3function wordPatternMatch(pattern, str) {
4 return isMatch(pattern, 0, str, 0, {}, new Set());
5
6 function isMatch(pattern, i, str, j, map, set) {
7 if (i == pattern.length && j == str.length) return true;
8 if (i == pattern.length || j == str.length) return false;
9
10 let c = pattern.charAt(i);
11 if (map[c]) {
12 if (!str.startsWith(map[c], j)) return false;
13 return isMatch(pattern, i + 1, str, j + map[c].length, map, set);
14 }
15
16 for (let k = j; k < str.length; k++) {
17 let p = str.substring(j, k + 1);
18 if (set.has(p)) continue;
19
20 map[c] = p;
21 set.add(p);
22 if (isMatch(pattern, i + 1, str, k + 1, map, set)) return true;
23
24 set.delete(p);
25 delete map[c];
26 }
27
28 return false;
29 }
30}
Note the key differences due to JavaScript syntax. In JavaScript, map[c]
is used instead of Python's char_to_str_map[pattern[i]]
to get pattern[i]'s value in map and delete map[c]
removes map[c] from map.
Java
In Java, we can use a HashMap to store our character-substring mappings, and a HashSet to store the substrings that have been mapped. Just like in Python and JavaScript, we use recursion for the backtracking part of our algorithm.
1
2java
3public class Solution {
4 public boolean wordPatternMatch(String pattern, String str) {
5 Map<Character, String> map = new HashMap<>();
6 Set<String> set = new HashSet<>();
7
8 return isMatch(pattern, 0, str, 0, map, set);
9 }
10
11 private boolean isMatch(String pattern, int i, String str, int j, Map<Character, String> map, Set<String> set) {
12 if (i == pattern.length() && j == str.length()) return true;
13 if (i == pattern.length() || j == str.length()) return false;
14
15 char c = pattern.charAt(i);
16
17 if (map.containsKey(c)) {
18 String s = map.get(c);
19
20 if (!str.startsWith(s, j)) return false;
21
22 return isMatch(pattern, i + 1, str, j + s.length(), map, set);
23 }
24
25 for (int k = j; k < str.length(); k++) {
26 String p = str.substring(j, k + 1);
27
28 if (set.contains(p)) continue;
29
30 map.put(c, p);
31 set.add(p);
32
33 if (isMatch(pattern, i + 1, str, k + 1, map, set)) return true;
34
35 map.remove(c);
36 set.remove(p);
37 }
38
39 return false;
40 }
41}
This Java solution is pretty much the same as previous solutions. The notable difference is the use of contains
and remove
methods for checking and deleting existing mappings, respectively. This is due to the syntax and standard methods provided by Java for HashMap and HashSet.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.