Word Pattern II

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:

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

Notes: You may assume both pattern and str contains only lowercase letters.

Solution

public class Solution {
    Map<Character, String> map = new HashMap<>();
    Set<String> set = new HashSet<>();
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern.isEmpty() && str.isEmpty()) {
            return true;
        } else if (pattern.isEmpty()) {
            return false;
        } else if (str.isEmpty()) {
            return false;
        } else {
            Character currentChar = pattern.charAt(0);
            if (map.containsKey(currentChar)) {
                String match = map.get(currentChar);

                if (str.length() >= match.length() && match.equals(str.substring(0, match.length()))) {
                    return wordPatternMatch(pattern.substring(1), str.substring(match.length()));
                } else {
                    return false;
                }
            } else {
                for (int i = 1; i <= str.length(); i++) {
                    String potential = str.substring(0,i);
                    if (set.contains(potential)) {
                        continue;
                    }

                    map.put(currentChar, str.substring(0, i));
                    set.add(str.substring(0, i));

                    boolean result = wordPatternMatch(pattern.substring(1), str.substring(i));
                    map.remove(currentChar);
                    set.remove(str.substring(0, i));

                    if (result) {
                        return true;
                    }
                }

                return false;
            }
        }
    }
}