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:

1. pattern = "abab", str = "redblueredblue" should return true.
2. pattern = "aaaa", str = "asdasdasdasd" should return true.
3. pattern = "aabb", str = "xyzabcxzyabc" should return false.
   Notes:
   You may assume both pattern and str contains only lowercase letters.

一刷
题解：
我们用map来保存pattern中的character代表的string, 然后对接下来的做匹配，如果不满足，就把该匹配从map中删除。
110ms

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();//pattern a represent the string
        Set<String> set = new HashSet<>();
        return isMatch(str, 0, pattern, 0, map, set);
    }
    
    private boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map,
                           Set<String> set){
        //base case
        if(i == str.length() && j == pat.length()) return true;
        if(j == str.length() || j == pat.length()) return false;
        
        char c = pat.charAt(j);
        
        if(map.containsKey(c)){
            String s = map.get(c);
            
            //check if we can use it to match str[i,..., i+s.length()]
            //startWith: begin at i, start with s
            if(!str.startsWith(s, i)) return false;
            
            return isMatch(str, i+s.length(), pat, j+1, map, set);
        }
        
        // pattern character does not exist in the map
        for(int k = i; k<str.length(); k++){
            String p = str.substring(i, k+1);
            if(set.contains(p)) continue;
            
            //create or update it
            map.put(c, p);
            set.add(p);
            
            // continue to match the rest
            if(isMatch(str, k+1, pat, j+1, map, set)) return true;
            
            map.remove(c);
            set.remove(p);
        }
        
        return false;
    }
}

用map的containsValue的方法来取代set, 按道理从set中寻找应该会更快，因为containsValue需要遍历。然而反而却慢了。
103ms

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();//pattern a represent the string
        return isMatch(str, 0, pattern, 0, map);
    }
    
    private boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map){
        //base case
        if(i == str.length() && j == pat.length()) return true;
        if(j == str.length() || j == pat.length()) return false;
        
        char c = pat.charAt(j);
        
        if(map.containsKey(c)){
            String s = map.get(c);
            
            //check if we can use it to match str[i,..., i+s.length()]
            //startWith: begin at i, start with s
            if(!str.startsWith(s, i)) return false;
            
            return isMatch(str, i+s.length(), pat, j+1, map);
        }
        
        // pattern character does not exist in the map
        for(int k = i; k<str.length(); k++){
            String p = str.substring(i, k+1);
            if(map.containsValue(p)) continue;
            
            //create or update it
            map.put(c, p);
            
            // continue to match the rest
            if(isMatch(str, k+1, pat, j+1, map)) return true;
            
            map.remove(c);
        }
        
        return false;
    }
}

应该还有更快的方法，留给二刷

二刷
首先能直观想到的办法，backtracking

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();
        str = str.trim();
        return bt(pattern, 0, str, 0, map, set);
    }
    
    private boolean bt(String pattern, int pPos, String str, int pStr, Map<Character, String> map, Set<String> set ){
        if(pPos == pattern.length() && pStr == str.length()) return true;
        if(pPos == pattern.length()) return false;
        if(pStr == str.length()) return false;
        if(map.containsKey(pattern.charAt(pPos))){
            String match = map.get(pattern.charAt(pPos));
            if(!str.substring(pStr).startsWith(match)) return false;
            else{
                return bt(pattern, pPos+1, str, pStr + match.length(), map, set);
            }
        }
        else{
            for(int i=pStr; i<str.length(); i++){
                String sub = str.substring(pStr, i+1);
                if(set.contains(sub)) continue;
                map.put(pattern.charAt(pPos), sub);
                set.add(sub);
                if(bt(pattern, pPos+1, str, i+1, map, set)) return true;;
                map.remove(pattern.charAt(pPos));
                set.remove(sub);
            }
        }
        return false;
    }
}