题目链接

英文链接：https://leetcode.com/problems/word-pattern/

中文链接：https://leetcode-cn.com/problems/word-pattern/

题目详述

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

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

示例1:

1 2	输入: pattern = "abba", str = "dog cat cat dog" 输出: true

示例 2:

1 2	输入:pattern = "abba", str = "dog cat cat fish" 输出: false

示例 3:

1 2	输入: pattern = "aaaa", str = "dog cat cat dog" 输出: false

示例 4:

1 2	输入: pattern = "abba", str = "dog dog dog dog" 输出: false

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

题目详解

运用一个 map 存储字符到字符串的映射。
由于是双向映射，必须两个方向同时满足条件或同时不满足条件。
遍历 pattern 的每一个字符，查看映射关系。
若 map 中存在字符 c 到 str 的映射，则当前字符串必须等于 str，否则不匹配，返回 false。通过 map.get(c).equals(split[i]) 判断，时间复杂度为 O(1)。
若 map 中不存在字符 c 到 str 的映射，则当前字符串必须不等于 str，否则不匹配，返回 false。通过 map.containsValue(split[i])判断，时间复杂度为 O(n)。
遍历结束没有发现不匹配的情况返回 true。

public class LeetCode_00290 {

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

由于是双向映射，运用两个 map 来存储映射关系是更好的选择。
并且，可以改变映射关系，通过映射到索引来进行判断。
若映射到不是同一个索引，说明不匹配。
表示不存在的索引需要单独指定，与其他索引不冲突，本题用 -1 表示。
注意 Integer 等包装类的对象判断相等要用 equals 进行比较，否则会出错（特别是超过 [-128, 127] 这个范围）。

public class LeetCode_00290 {

    public boolean wordPattern(String pattern, String str) {
        String[] split = str.split(" ");
        if (pattern.length() != split.length) {
            return false;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); ++i) {
            char c = pattern.charAt(i);
            // 注意 Integer 间的比较用 equals，不要用 ==
            if (!map1.getOrDefault(c, -1).equals(map2.getOrDefault(split[i], -1))) {
                return false;
            }
            map1.put(c, i);
            map2.put(split[i], i);
        }
        return true;
    }
}