Word Pattern I & II

Word Pattern

热手题，对于 bijection mapping 就是两个 hashmap 互相查，和 Isomorphic Strings 一样。

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<String, String> pat2word = new HashMap<>();
        HashMap<String, String> word2pat = new HashMap<>();

        String[] strs = str.split(" ");
        if(strs.length != pattern.length()) return false;

        for(int i = 0; i < strs.length; i++){
            String pat = "" + pattern.charAt(i);
            String word = strs[i];

            if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
                pat2word.put(pat, word);
                word2pat.put(word, pat);
            } else {
                if(!pat2word.containsKey(pat)) return false;
                if(!word2pat.containsKey(word)) return false;

                if(!pat2word.get(pat).equals(word)) return false;
                if(!word2pat.get(word).equals(pat)) return false;
            }
        }

        return true;
    }
}

Word Pattern II

犯错1：没考虑到当前的 pat / word 都在 map 里而且合法的情况，这时候需要继续向下探。

犯错2: pattern.length() == 0 代表着搜索的结束，但是不是 return true 的充分条件。所以要在 pattern 为 0 的时候正确结束免得越界，同时也要检查 str.length() 是否也等于 0.

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

    private boolean dfs(String pattern, String str, 
                        HashMap<String, String> pat2word, 
                        HashMap<String, String> word2pat){

        if(pattern.length() == 0) return (str.length() == 0);

        String pat = "" + pattern.charAt(0);

            for(int j = 0; j < str.length(); j++){
                String word = str.substring(0, j + 1);
                if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
                    pat2word.put(pat, word);
                    word2pat.put(word, pat);

                    if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;

                    pat2word.remove(pat);
                    word2pat.remove(word);
                } else if(pat2word.containsKey(pat) && word2pat.containsKey(word)){
                    if(pat2word.get(pat).equals(word) && word2pat.get(word).equals(pat)){
                        if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
                    }
                } 
                /*
                else {
                    if(!pat2word.containsKey(pat))  continue;
                    if(!word2pat.containsKey(word)) continue;

                    if(!pat2word.get(pat).equals(word)) continue;
                    if(!word2pat.get(word).equals(pat)) continue;
                }
                */
            }

        return false;
    }
}

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

然而下面的代码用时上和原来的没什么不同。。可能是 test case 数量太小吧。面试被问到时作为一个 follow up 优化写上去还是不错的。

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

    private boolean dfs(String pattern, String str, 
                        HashMap<String, String> pat2word, 
                        HashMap<String, String> word2pat){

        if(pattern.length() == 0) return (str.length() == 0);

        String pat = "" + pattern.charAt(0);

        if(pat2word.containsKey(pat)){
            String word = pat2word.get(pat);
            if(word.length() > str.length()) return false;

            else if(word.equals(str.substring(0, word.length()))){
                if(dfs(pattern.substring(1), str.substring(word.length()), pat2word, word2pat)) return true;
            } else {
                return false;
            }
        }

            for(int j = 0; j < str.length(); j++){
                String word = str.substring(0, j + 1);
                if(!pat2word.containsKey(pat) && !word2pat.containsKey(word)){
                    pat2word.put(pat, word);
                    word2pat.put(word, pat);

                    if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;

                    pat2word.remove(pat);
                    word2pat.remove(word);
                } else if(pat2word.containsKey(pat) && word2pat.containsKey(word)){
                    if(pat2word.get(pat).equals(word) && word2pat.get(word).equals(pat)){
                        if(dfs(pattern.substring(1), str.substring(j + 1), pat2word, word2pat)) return true;
                    }
                } 
                /*
                else {
                    if(!pat2word.containsKey(pat))  continue;
                    if(!word2pat.containsKey(word)) continue;

                    if(!pat2word.get(pat).equals(word)) continue;
                    if(!word2pat.get(word).equals(pat)) continue;
                }
                */
            }

        return false;
    }
}