My code:

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null) {
            return false;
        }
        return helper(pattern, str, 0, 0, new HashMap<Character, String>(), new HashSet<String>());
    }
    
    private boolean helper(String p, String s, int index, int begin, HashMap<Character, String> map, HashSet<String> set) {
        if (index == p.length() && begin == s.length()) {
            return true;
        }
        else if (index == p.length() || begin == s.length()) {
            return false;
        }
        
        char curr = p.charAt(index);
        if (map.containsKey(curr)) {
            String val = map.get(curr);
            if (s.substring(begin).startsWith(val)) {
                return helper(p, s, index + 1, begin + val.length(), map, set);
            }
            else {
                return false;
            }
        }
        else {
            for (int i = begin; i < s.length(); i++) {
                String next = s.substring(begin, i + 1);
                if (set.contains(next)) {
                    continue;
                }
                else {
                    set.add(next);
                    map.put(curr, next);
                    boolean flag = helper(p, s, index + 1, begin + next.length(), map, set);
                    if (flag) {
                        return true;
                    }
                    set.remove(next);
                    map.remove(curr);
                }
            }
            return false;
        }
    }
}

reference:
https://discuss.leetcode.com/topic/26750/share-my-java-backtracking-solution/2

這道題目沒能做出來不應該的。
其實和
Regular Expression
Wildcard Matching
很相似申尼，都是 pattern match的問題祥绞。然后都需要 backtracking

只不過我一開始想的是荆残，string 做key饮亏， character 做value
這樣的話渔伯，每次dfs爆价，對于string担汤，就需要傳入begin, end兩個參數(shù)。有點麻煩
然后這里的話反了下明也。
好處是宣虾，
當我們拿到這一層的character 時，如果hashtable中存在這個key温数，那么取出value绣硝，判斷當前string是否 startsWith(value)
如果是，就進入下一級帆吻，如果不是域那，就返回false

如果hashtable 不存在這個key
那么就需要用 backtracking 標志性的 for-loop
遍歷每種情況。
同時猜煮，不同的key不同映射到同個string次员，用這個條件可以減去some branch to reduce the time

差不多就這樣了。

Anyway, Good luck, Richardo! -- 09/19/2016