291 Word Pattern II

291. 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.

分析& 代码

discuss里面这个写法实在写的太逻辑清晰了， 一看就懂

一看Helper的签名就能做了哈哈

helper的含义是

如果刚好pattern和str都同时到达了尽头，说明匹配上了，返回true

　　如果两个中只有一个到达了尽头，说明没有匹配上，返回false

　　如果在map里面已经有目前这个pattern字母对应的str串

　　　　那么如果当前的str并不以那个开头，说明就没有匹配上返回false
　　　　否则就返回helper(str, i往前移动当前字母小pattern的长度，pattern, j往前一格，map, set)
　　否则

　　　　就对从目前为止开始的str开始，试所有可能的长度的str和当前的pattern对应
　　　　　　如果这个小str已经被匹配给某个pattern字母了，返回false
　　　　　　在set和map里加入目前的组合
　　　　　　如果递归发现匹配上了，就返回true
　　　　　　不然就从set和map里面把当前组合移除
　　　　返回false（因为试了目前str所有的情况试图和当前的pattern字母匹配）

代码如下：

public boolean wordPatternMatch(String pattern, String str) {
    if(pattern == null || str == null) {
        return false;
    }
    Map<Character, String> map = new HashMap<>();
    Set<String> set = new HashSet<>();
    return match(str, 0, pattern, 0, map, set);
}

private boolean match(String str, int i, String pattern, int j, Map<Character, String> map, Set<String> set) {
    if(i == str.length() && j == pattern.length()) {
        return true;
    }
    if(i == str.length() || j == pattern.length()) {
        return false;
    }
    char c = pattern.charAt(j);
    if(map.containsKey(c)) {
        String pat = map.get(c);
        if(!str.startsWith(pat, i)) {
            return false;
        }
        return match(str, i + pat.length(), pattern, j + 1, map, set);
    } else {
        for(int k = i; k < str.length(); k++) {
            String pat = str.substring(i, k + 1);
            if(set.contains(pat)) {
                continue;
            }
            map.put(c, pat);
            set.add(pat);
            if(match(str, i + pat.length(), pattern, j + 1, map, set)) {
                return true;
            }
            map.remove(c);
            set.remove(pat);
        }
        return false;
    }
}