291. Word Pattern II

Problem:

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.

Analysis:

This problem is the recursive implementation of Word Pattern. Again, we can eliminate the index counter while doing dfs. 

Solution: 

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        return isMatch(pattern, str, new HashMap<>(), new HashSet<>());
    }

    private boolean isMatch(String pat, String str, Map<Character, String> map, Set<String> set) {
        if (str.length() == 0 && pat.length() == 0)
            return true;
        if (str.length() == 0 || pat.length() == 0)
            return false;

        char c = pat.charAt(0);
        if (map.containsKey(c)) {
            String sub = map.get(c);
            if (str.startsWith(sub, 0)) {
                return isMatch(pat.substring(1), str.substring(sub.length()), map, set);
            } else {
                return false;
            }
        }

        for (int i = 0; i < str.length(); i++) {
            String sub = str.substring(0, i + 1);
            // exist in prev pattern
            if (set.contains(sub))
                continue;
            // new pattern
            set.add(sub);
            map.put(c, sub);
            if (isMatch(pat.substring(1), str.substring(i + 1), map, set)) {
                return true;
            }
            set.remove(sub);
            map.remove(c);
        }

        return false;
    }
}