0291. Word Pattern II

https://leetcode.com/problems/word-pattern-ii

Description

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 = "abab", s = "asdasdasdasd"
**Output:** true
**Explanation:** One possible mapping is as follows:
'a' -> "a"
'b' -> "sdasd"
Note that 'a' and 'b' cannot both map to "asd" since the mapping is a bijection.

Example 4:

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

Constraints:

• 1 <= pattern.length, s.length <= 20

• pattern and s consist of only lower-case English letters.

ac

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();

        return backtrack(pattern, 0, str, 0, map, set);
    }
    private boolean backtrack(String pattern, int pstart, String str, int sstart, Map<Character, String> map, Set<String> set) {
        // exit, reach the end
        if (pstart >= pattern.length() || sstart >= str.length()) {
            return pstart == pattern.length() && sstart == str.length(); // both should reach the end to say true
        }

        char curr = pattern.charAt(pstart);
        // in map, seen before
        if (map.containsKey(curr)) {
            String prev = map.get(curr);

            if (!str.startsWith(prev, sstart)) return false; // dont' match previous result, start over

            // matach, move on the next
            return backtrack(pattern, pstart+1, str, sstart + prev.length(), map, set);
        } 

        // not in map, try different strings in str
        for (int i = sstart; i < str.length(); i++) {
            String candidate = str.substring(sstart, i + 1);
            if (set.contains(candidate)) continue; // this string used by others before, skip it.
            map.put(curr, candidate);
            set.add(candidate);

            if (backtrack(pattern, pstart+1, str, i + 1, map, set)) return true;

            map.remove(curr);
            set.remove(candidate);
        }

        return false; // cant match, false
    }
}