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 and s (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 in s. If they do not match, we return False, else we call isMatch 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 at j. We continue to do this until we find a match or exhaust all possibilities, in which case we return False.## 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.