WordPattern [source code]

public class WordPattern {
static
/******************************************************************************/
public class Solution {
    public boolean wordPattern(String pattern, String str) {
        if (pattern.length() == 0 || str.length() == 0) return false;
        String[] patArray = pattern.split(""), strArray = str.split(" ");
        if (patArray.length != strArray.length) return false;
        int[] patPattern = buildPattern(patArray);
        int[] strPattern = buildPattern(strArray);
        for (int i = 0; i < strArray.length; i++) {
            if (patPattern[i] != strPattern[i]) return false;
        }
        return true;
    }

    public int[] buildPattern(String[] strs) {
        Map<String, Integer> map = new HashMap<>();
        int[] res = new int[strs.length];
        int tail = 0;
        int code = 0;
        for (String s : strs) {
            Integer num = map.get(s);
            if (num == null) {
                num = code;
                map.put(s, code++);
            }
            res[tail++] = num;
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        WordPattern.Solution tester = new WordPattern.Solution();
        String[] inputs = {
            "", "", //false;
            "abba", "", //false
            "abba", "dog cat cat dog", //true
            "abba", "dog cat cat fish", //false
            "aaaa", "dog cat cat dog", //false
            "abba", "dog dog dog dog", //false
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s1 = inputs[2 * i];
            String s2 = inputs[1 + 2 * i];
            System.out.println(s1 + " VS " + s2 + " -> " + tester.wordPattern(s1, s2));
        }
    }
}

这么简单的题目最后还是想太多, 花了不少时间. 也没有想到什么可以彻底避免用 Map 的思路; 除开这些优化的考虑, 整个问题还是很简单的.

注意 split 的用法:

java> "abba".split(" ")  
java.lang.String[] res0 = ["abba"]  
java> "abba".split("")  
java.lang.String[] res1 = ["a", "b", "b", "a"]

这里为了 API 的统一, 我希望 pat 也被 split 成一个string array, 而不是一个char array, 上面的代码就是展示了怎么做这个 split;

另外这里的这个 helper 本来按照我的直觉是返回 string 的, 不过想想 string 除了看起来简洁, 好像也没有多少什么其他的优点了, 最后还是决定这个 pattern 返回的是一个int array, 虽然看起来没有 string 简洁, 不过最后速度上应该稍微有些优势. 而且这里这个 array 的 size 是可以提前知道的, 所以很合适;

最后的速度是3ms (18%), 估计还是有更好的做法;

这个是 submission 最优解: 2(35)

public class Solution {  
    public boolean wordPattern(String pattern, String str) {  
        String[] hm=new String[26];  
        char[] cp=pattern.toCharArray();  
        Set<String> sets=new HashSet<String>();  
        String[] strp=str.split(" ");  
        if(cp.length!=strp.length) return false;  
        for(int i=0;i<cp.length;i++){  
            if(hm[cp[i]-'a']!=null){  
                if(!hm[cp[i]-'a'].equals(strp[i])) return false;  
            } else {  
                hm[cp[i]-'a'] = strp[i];  
                if(!sets.add(strp[i])) return false;  
            }      
        }  
        return true;  

    }  
}

这个算法的思路还是挺有意思的, 用的还是一个 hash 的思路. 这个思路我刚开始放弃了是感觉str 被 split 之后每一个 unit 应该是一个 string, 这个 string 不好用来作为 hash 的 index. 他这里采用的方法是用 string 作为 hash 的 value, 然后 index 还是用 pat 里面的 char. 然后他一个循环里面, 扫的是 pat 的 character, 然后建立bijection. 这个过程完成的内容其实是"如果知道了一个 char, 那么就知道了一个 string". 这个还不足够, 我们还要证明"如果知道了一个 string, 也就唯一确定了一个 char". 这个过程的实现就是指望同一个 string 至多只能作为一个 char 的 value. 来检查这个的方法他用的是 set;

这个是 discussion 里面类似这个的一个做法:

public class Solution {  
    public boolean wordPattern(String pattern, String str) {  
        String[] arr= str.split(" ");  
        HashMap<Character, String> map = new HashMap<Character, String>();  
        if(arr.length!= pattern.length())  
            return false;  
        for(int i=0; i<arr.length; i++){  
            char c = pattern.charAt(i);  
            if(map.containsKey(c)){  
                if(!map.get(c).equals(arr[i]))  
                    return false;  
            }else{  
                if(map.containsValue(arr[i]))  
                    return false;  
                map.put(c, arr[i]);  
            }      
        }  
        return true;  
    }  
}

但是这个做法的一个问题是 contains Value 是要求一个O(N) 的扫描的, 所以这样的做法最后的速度就不好; 比较好的做法就是把 value(string) 单独存下来在一个 set 里面(也有人用一个反向 map 来保存, 不过不知道containsKey的速度是不是就比containsValue快?);

这个是 discussion 里面一个很简练的解:

public boolean wordPattern(String pattern, String str) {  
    String[] words = str.split(" ");  
    if (words.length != pattern.length())  
        return false;  
    Map index = new HashMap();  
    for (Integer i=0; i<words.length; ++i)  
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i))  
            return false;  
    return true;  
}

这个解的一个核心思路就是maintain rightmost occurrence, 这个前面碰到过不止一次了, maintain rightmost occurrence indices其实就等价于maintain all occurrence indices, 这个最后完成的一个效果就是check for full match 的作用;
他这里还使用了另外一个小技巧就是他这里的 map 并没有指定类型, 而是使用 Object 的 generic 来处理, 这样就可以只使用一个 Map 就完成这里的要求;
另外, 关于他这里的 put 的返回值的使用:

java> Map map = new HashMap()  
java.util.Map map = {}  
java> map.put('a', 0)  
java.lang.Object res1 = null  
java> map.put('a', 1)  
java.lang.Integer res2 = 0  
java> map  
java.util.Map map = {a=1}  
java> map.put('b', 1)  
java.lang.Object res3 = null  
java> map.put('b',2)  
java.lang.Integer res4 = 1  
java> map  
java.util.Map map = {a=1, b=2}

所以他这里一个check put == put的操作直接就把 check 跟 update 同时完成了; 这个是作者自己对此的解释:
Yes, only few people seem to know that Map.put and Set.add return something. I often see unnecessary if (!map.containsKey(...)) or if (!set.contains(...))before putting or adding :-P

这个帖子很有意思, 这个是下面一个人贴的稍微 dumb 一点的一个版本:

public class Solution {  
    public boolean wordPattern(String pattern, String str) {  
        String[] strs = str.split(" ");  
        HashMap<String, Integer> mapstr = new HashMap<String, Integer>();  
        HashMap<Character, Integer> mapc = new HashMap<Character, Integer>();  
        if(pattern.length() != strs.length) return false;  
        for(int i = 0; i < pattern.length(); i++){  
            char tmpc = pattern.charAt(i);  
            String tmpstr = strs[i];  
            if((mapc.containsKey(tmpc) ^ mapstr.containsKey(tmpstr))  
                ||(mapc.containsKey(tmpc) && mapstr.containsKey(tmpstr) && mapc.get(tmpc) != mapstr.get(tmpstr))) return false;  
            mapc.put(tmpc, i);  
            mapstr.put(tmpstr, i);  
        }  
        return true;  
    }  
}

他这个版本的原因是因为他用了 != 而不是 equals来判断 get 出来的两个东西; 不过下面他们开始讨论 equals 了;

底下有人认为, 既然 put 如果成功的话, 返回出来的反正都是 int, 为什么不能直接用==? 但是实际上不是这样的, 可以看我上面的 repl 的 log, put 返回出来的其实是 Integer, 这个属于 object. 然后有人认为既然是 object 肯定要用 equals 来 dereference. 但是下面有人讨论:

关于 autoboxing, 底下有所讨论:
Just want to point out one thing about autoboxing. As mentioned by @StefanPochmann, we can try such an example:

int i = 10;  
Integer a = i;  
Integer b = i;  
System.out.println(a == b); //guess what is the output?

The output was supposed to be false. However, you can test this and you will find it is true.
Why?

Because "The JVM is caching Integer values. == only works for numbers between -128 and 127 "
Then you can try another code:

int i = 1000; //greater than 127  
Integer a = i;  
Integer b = i;  
System.out.println(a == b); //this time we got false

Look, now you get false. And now it explains why we can pass the small cases (because the indices are in the range of -128 and 127). We also know why it cannot pass the larger test case.

也就是如果是小的 case, 这个是可以成立的, 但是超过128的 case(应该是constituents count超过128), == 判断就不行了, 这个也是代码原作者po 代码的时候指出的自己的 fail case, 都是大 case;

这个是正确代码的作者之前的一次更改:
Switched from

for (int i=0; i<words.length; ++i)  
    if (!Objects.equals(index.put(pattern.charAt(i), i),  
                        index.put(words[i], i)))  
        return false;

to the current version with i being an Integer object, which allows to compare with just != because there's no autoboxing-same-value-to-different-objects-problem anymore. Thanks to lap_218 for somewhat pointing that out in the comments.
这个意思是因为 map 吐出来的肯定是一个 object, 所以如果你 put 进去的是一个 int, 最后吐出来给你的是一个 Integer, 是被 autobox 之后的一个, 这个可能会造成两个 Integer 虽然对应的 value 是想等的, 但是实际上两个 object 本身并不想等; (这个上面已经讨论过了, 当 int 的 value 超过128之后, 没有 caching, 就会发生这种情形了);

这个是一个人针对这个更改提出的疑问(要不说 discussion 里面的人还是钻的深):
In the first version, why does Objects.equals() work,

but index.put(pattern.charAt(i), i).equals(index.put(words[i], i)) not?

Does the put() method auto-unbox the primitives? 'Cuz the later one will throw Null Pointer Exception, while Object.equals() won't.

他自己后来回复:
After dig into the source code, I found that Objects.equals(Object a, Object b) and Object.equals(Object o) have different behaviors:

// java.util.Objects  
 public static boolean equals(Object a, Object b) {  
     return (a == b) || (a != null && a.equals(b));  
 }

But

// java.lang.Object  
public boolean equals(Object obj) {  
    return (this == obj);  
}

So the reason that only Objects.equals(Object a, Object b) works is it can handle null case.

作者回复:
You didn't have to dig into that source code, index.put(pattern.charAt(i), i) can be null, which simply doesn't have any methods that could be called. That said, I do like people not afraid to dig into those sources :-)

其实也就是避免了一个dot on null的问题;

Problem Description

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 word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Credits:
Special thanks to @minglotus6 for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:78.6K
Total Submissions:239K
Contributor: LeetCode
Companies
dropbox uber
Related Topics
hash table
Similar Questions
Isomorphic Strings Word Pattern II