290. Word Pattern(单词模式)（Integer的坑）

题目地址：https://leetcode.com/problems/word-pattern/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 patternand a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"

Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"

Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"

Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"

Output: false

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"

输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"

输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"

输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"

输出: false

说明:
你可以假设 pattern 只包含小写字母， str 包含了由单个空格分隔的小写字母。 

class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] s = str.split(" ");
        if (s.length != pattern.length())
            return false;
        int len = s.length;
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        for (Integer i = 0; i < len; ++i) { // 一定要用Integer而不是int类型，聪明的你有没有看出为什么？
            if (map1.put(s[i], i) != map2.put(pattern.charAt(i) + "", i))
                return false;
        }
        return true;
    }
}

查看api文档   V put(K key, V value)

返回：上一次与 key 关联的值，如果没有针对 key 的映射关系，则返回 null。（如果该实现支持 null 值，则返回 null 也可能表示此映射以前将 null 与 key 关联）。

举例说明：

import java.util.HashMap;
import java.util.Map;
public class test1 {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        System.out.println(map.put("a", 1));
        System.out.println(map.put("b", 2));
        System.out.println(map.put("a", 3));
        System.out.println(map.put("b", 4));
        System.out.println(map.put("c", 22));
    }
}

运行结果：

第一次put进去“a”和“b”，之前没有put过“a”“b”所以返回null。

接着put进“a”的时候，上次put的“a”的值是1，所以返回1

put进“b”的时候，上次put的“b”的值是2，所以返回2

再put进“c”的时候，之前没有建立映射关系，所以仍然返回null

所以我相信大家能懂上面的程序。

为什么不用一个map装，而要用2个呢？（如果不熟悉可以百度搜map的put用法）

因为可能值和键相同。pattern=“abc”，而String=“c b a”确实是符合pattern模式的串，但是却返回false

因为只有1个map，之前装过a，再次装a就会返回i=0.而不是null（原本想返回null的）

题目坑在哪里？

我怎么都没想到会在for循环出现。

有一个测试用例如下：

pattern="ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccdd";
str = "s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s
 s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s s t t";

一共130个字符

但是查看java.lang.Integer的源代码：

static final Integer[] cache = new Integer[-(-128) + 127 + 1];

static {

    for (int i = 0; i < cache.length; ++i){

          cache[i] = new Integer(i - 128);

    }

}

系统把一个-128~127之间的整数自动装箱成Integer实例，并放入了一个名为cache的数组缓存起来，如果把一个-128~127之间的整数自动装箱成一个Integer实例时，实际上是直接指向对应的数组元素，因此-128~127之间的同一个整数自动装箱成Integer实例时，永远都是引用cache数组的同一个数组元素，所以它们全部相等。但是每次把不在-128~127范围的数自动装箱成Integer实例时，系统总是重新创建一个Integer实例。

上面有一个测试用例是长度130>128，所以如果是i的类型是int而不是Integer，那么等到i=128时，实际自动装箱进去的都是new Integer的一个新对象，他们是不相等的，所以会返回false！！而for循环的i是Integer类型的put进去的时候就不会再次自动装箱！是引用之间的赋值，所以两个Integer是相等的（如不太理解可以自行百度int和Integer的差别）

Debug code in playground:

class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] s = str.split(" ");
        if (s.length != pattern.length())
            return false;
        int len = s.length;
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        for (Integer i = 0; i < len; ++i) {
            if (map1.put(s[i], i) != map2.put(pattern.charAt(i) + "", i))
                return false;
        }
        return true;
    }
}

public class MainClass {
    public static String stringToString(String input) {
        if (input == null) {
            return "null";
        }
        return Json.value(input).toString();
    }
    
    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            String pattern = stringToString(line);
            line = in.readLine();
            String str = stringToString(line);
            
            boolean ret = new Solution().wordPattern(pattern, str);
            
            String out = booleanToString(ret);
            
            System.out.print(out);
        }
    }
}

============================Talk is cheap, show me the code=========================