WordPatternII.java

    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null) {
            return false;
        }

        Map<Character, String> lookup = new HashMap<>();
        Set<String> dup = new HashSet<>();

        return this.isMatch(pattern, str, lookup, dup);
    }

    // DFS recursion to list out all the possibilities
    public boolean isMatch(String pattern, String str, Map<Character, String> lookup, Set<String> dup) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }

        char c = pattern.charAt(0);

        if (lookup.containsKey(c)) {
            String mappedString = lookup.get(c);
            if (mappedString.length() > str.length()) {
                return false;
            }

            // could use str.startsWith(mappedString)
            if (!mappedString.equals(str.substring(0, mappedString.length()))) {
                return false;
            }

            return this.isMatch(pattern.substring(1), str.substring(mappedString.length()), lookup, dup);

        } else {
            for (int i = 1; i <= str.length(); i++) {
                String mappingString = str.substring(0, i);
                if (dup.contains(mappingString)) {
                    // not a bijection mapping, not not return false, but continue
                    continue;
                }

                lookup.put(c, mappingString);
                dup.add(mappingString);
                if (this.isMatch(pattern.substring(1), str.substring(i), lookup, dup)) {
                    return true;
                }
                // reset value for next recursion iteration for backtracking
                lookup.remove(c);
                dup.remove(mappingString);
            }
        }

        return false;
    }