Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty substring instr.

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if(pattern == null && str == null)
            return true;
        if(pattern == null || str == null)
            return false;

        HashMap<Character, String> forward = new HashMap<>();
        HashMap<String, Character> reverse = new HashMap<>();

        return helper(forward, reverse, 0, 0, pattern, str);
    }

    public boolean helper(HashMap<Character, String> forward, HashMap<String, Character> reverse, int p, int s, String pattern, String str) {
        if(p == pattern.length() && s == str.length())
            return true;

        if(p == pattern.length() || s == str.length())
            return false;

        char c = pattern.charAt(p);
        if(forward.containsKey(c)) {
            String target = forward.get(c);
            if(s + target.length() > str.length())
                return false;;

            if(!str.substring(s, s + target.length()).equals(target))
                return false;

            return helper(forward, reverse, p + 1, s + target.length(), pattern, str);
        } else {
            for(int i = s + 1; i <= str.length(); i++) {
                String next = str.substring(s, i);
                if(reverse.containsKey(next))
                    continue;

                forward.put(c, next);
                reverse.put(next, c);
                if(helper(forward, reverse, p + 1, i, pattern, str))
                    return true;
                forward.remove(c);
                reverse.remove(next);
            }
        }

        return false;
    }
}