Word Pattern II

给一个pattern和一个string, 问string是否满足pattern. 这次string里面的word没有空格.

所以我们要backtracking所有的可能的string的组合, 对于每个组合, 我们都需要添加到hashmap中, 这里, 我们在遍历pattern和string时, 要同时记录pattern中每个char对应在pattern的位置和当前string中substring对应的pattern的位置. 通过string和pattern在pattern中的位置i来判断是否相同. 为了区分pattern和string, 我们可以同两个hashmap, 也可以用一个, 用一个的时候, 注意要用

HashMap<Object,Integer> map

因为pattern存的是<char,integer>,而string存的是<string,integer>, 所以用一个hashmap可以通过比较类型来区别key是pattern或string.

其实是这题和word pattern都是isomorphic问题.

 public boolean wordPatternMatch(String pattern, String str) {
        HashMap map = new HashMap();
        return dfs(pattern, 0, str, 0, map);
    }
    private boolean dfs(String pattern, int i, String str, int j, HashMap map){
        if(i == pattern.length() && j == str.length()){// 如果刚好搜完. 返回true
            return true;
        }
        if(i == pattern.length() || j == str.length()){// 如果一个完了, 另一个没完, 返回false
            return false;
        }
        char c = pattern.charAt(i);
        for(int k = j; k < str.length(); k++){
            if(map.get(c) == map.get(str.substring(j, k+1))){//如果map中的i对应的值(可以是null) 和 sbustring对应的值相同(也可以是null)
                Integer val = (Integer)map.get(c);
                if(val == null){//如果是null
                    map.put(pattern.charAt(i), i);//把pattern的<char,integer>放map中
                    map.put(str.substring(j, k+1), i);//把string的<string,integer>放map中
                }
                if(dfs(pattern, i+1, str, k+1, map)){//dfs
                    return true;
                }
                if(val == null){// backtracking
                    map.remove(pattern.charAt(i));
                    map.remove(str.substring(j, k+1));
                }
            }
        }
        return false;
    }