291. Word Pattern II

/*
Refer: https://leetcode.com/problems/word-pattern-ii/discuss/73664/Share-my-Java-backtracking-solution

Time Complexity:
T(N) = T(N-1) + O(M)
T(N) = N*M + 1 = O(N*M)

Space Complexity: O(N + M)

N = Length of pattern
M = Length of string
*/
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null) {
            return false;
        }
        if (pattern.length() == 0 && str.length() == 0) {
            return true;
        }

        return isMatch(str, 0, pattern , 0, new HashMap<Character, String>(), new HashSet<String>());
    }

    public boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map, Set<String> set) {
        if (i == str.length() && j == pat.length()) {
            return true;
        }
        if (i == str.length() || j == pat.length()) {
            return false;
        }

        char curP = pat.charAt(j);

        if (map.containsKey(curP)) {
            String s = map.get(curP);

            if (!str.startsWith(s, i)) {
                return false;
            }

            return isMatch(str, i+s.length(), pat, j+1, map, set);
        }

        for (int k = i; k < str.length(); k++) {
            String s = str.substring(i, k+1);

            if (set.contains(s)) {
                continue;
            }

            map.put(curP, s);
            set.add(s);

            if(isMatch(str, k+1, pat, j+1, map, set)) {
                return true;
            }

            map.remove(curP);
            set.remove(s);
        }

        return false;
    }
}