Thinking process

BackTrakcing

But how to avoid duplicates?

• using a hash set
• the containsValue of hash map is O(n)

Mistakes

when to return true? when to return false?

API

String

• startsWirth(String str, int index);

public class Solution {
    private HashMap<Character, String> map = new HashMap<>();
    private HashSet<String> exist = new HashSet<>();
    public boolean wordPatternMatch(String pattern, String str) {
        return wordPatternMatchHelper(pattern, str, 0, 0);
    }

    private boolean wordPatternMatchHelper(String pattern, String str, int index, int start) {
        if (start == str.length() && index == pattern.length()) return true;
        if (start == str.length() || index == pattern.length()) return false;


        char c = pattern.charAt(index);
        if (map.containsKey(c)) {
            String matchedStr = map.get(c);
            if (!str.startsWith(matchedStr, start)) {
                return false;
            }

            return wordPatternMatchHelper(pattern, str, index + 1, start + matchedStr.length());
        }

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

            if (exist.contains(matchStr)) {
                continue;
            }

            map.put(c, matchStr); 
            exist.add(matchStr);

            if (wordPatternMatchHelper(pattern, str, index + 1, i)) {
                return true;
            }

            map.remove(c);
            exist.remove(matchStr);
        }

        return false;

    }
}