# 0291. Word Pattern II
###### tags: `Leetcode` `Medium` `Backtracking`
Link: https://leetcode.com/problems/word-pattern-ii/
## 思路
用map存当下路径的pattern
用set保证两个字母不会对到同一个字符串
在backtracking的递归函数里面一旦往map或者set里加任何东西 一定要在递归之后把它从里面删掉
## Code

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        Map<Character, String> map = new HashMap<>();
        //to avoid use both 'a' and 'b' to represent same string
        Set<String> set = new HashSet<>();
        return dfs(pattern, s, 0, 0, map, set);
    }
    private boolean dfs(String pattern, String s, int p1, int p2, Map<Character, String> map, Set<String> set){
        if(p1==pattern.length() && p2==s.length()) return true;
        if(p1>=pattern.length() || p2>=s.length()) return false;
        if(map.containsKey(pattern.charAt(p1))){
            String p = map.get(pattern.charAt(p1));
            for(int i=0; i<p.length();i++){
                if(p2+i>=s.length() || s.charAt(p2+i)!=p.charAt(i)) return false;
            }
            return dfs(pattern, s, p1+1, p2+p.length(), map, set);
        }
        else{
            for(int i=p2; i<s.length(); i++){
                String newStr = s.substring(p2, i+1);
                if(set.contains(newStr)) continue;
                map.put(pattern.charAt(p1), newStr);
                set.add(newStr);
                if(dfs(pattern, s, p1+1, i+1, map, set)) return true;
                set.remove(newStr);
                map.remove(pattern.charAt(p1));
            }
        }
        return false;
    }
}