Word Pattern

Uber

要保证的是a -> dog, dog -> a

对于 bijection mapping 就是两个 hashmap 互相查。

pat和word需要做到一一对应。

可以用一个HashMap来实现，当hashmap有pat的时候，查看对应的string是否和hashmap里面存的一样。 当hashmap没有这个pat的时候，查看对应的string是否已经在hashmap里面存的values里面了。

Isomorphic Strings

Word Pattern II

就是word pattern I 再加上一个backtracking。

使用两个hashmap，程序更好写。

public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        return dfs(pattern, str, new HashMap<>(), new HashMap<>());
    }

    private boolean dfs(String pat, String str, HashMap<Character, String> patToWord, HashMap<String,Character> wordToPat) {
        // pattern.length() == 0 代表着搜索的结束，但不是 return true 的充分条件。所以要在 pattern 为 0 的时候正确结束免得越界，同时也要检查 str.length() 是否也等于 0.
        if(pat.length() == 0) return str.length() == 0;

        char p = pat.charAt(0);

        for(int i = 0; i < str.length(); i++) {
            String word = str.substring(0, i + 1);

            if(!patToWord.containsKey(p) && !wordToPat.containsKey(word)) {
                patToWord.put(p, word);
                wordToPat.put(word, p);

                if(dfs(pat.substring(1), str.substring(i + 1), patToWord, wordToPat)) return true;

                patToWord.remove(p);
                wordToPat.remove(word);
            } else if(patToWord.containsKey(p) && wordToPat.containsKey(word)) {
                if(patToWord.get(p).equals(word) && wordToPat.get(word) == p) {
                    if(dfs(pat.substring(1), str.substring(i + 1), patToWord, wordToPat)) return true;
                }
            }
        }
        return false;
    }
}

这种写法在速度上可以进一步改进，比如当看到 char 已经在 map 时，我们就直接把其对应的 word 取出来，没有问题的话就可以继续，否则可以立刻返回 false 进行剪枝和early termination.