题目链接

290. 单词规律

标签

哈希表 字符串

思路

本题与 205. 同构字符串 很像，要么使用 建立双向索引 的方法，要么使用 查找第一次出现索引 的方法。上面那道题是用 字符与字符 之间的索引比较，而本题则是使用 字符与字符串 之间的索引比较。

建立双向索引 的方法是一种容易想到的方法，它的核心思想就是分别使用两个 Map，分别记录从 pattern中的字符 到 s中的字符串 的映射和从 s中的字符串 到 pattern中的字符 的映射，然后截取每个 字符 与 字符串，查看 字符 与 字符串 能否 互相映射，如果 字符 或 字符串 没有映射，则先建立映射。

相比之下，查找第一次出现索引 这种方法更难想到，因为它更偏向 底层，上面的方法使用 Map 存储了 每个字符对应的第一个字符串 或 每个字符串对应的第一个字符，其实不需要这么复杂，只需要存储 每个字符第一次出现的位置 和 每个字符串第一次出现的位置 即可，因为比较 字符 与 字符串 能否 互相映射 的更底层就是 比较 字符第一次出现的索引 与 字符串第一次出现的索引 是否一致。

思路明确了：先将字符串 s 用空格分割为 list；然后检查 pattern中字符的个数 与 list中字符串的个数 是否相等，如果这两个值不相等，那就说明 pattern 和 s 不遵循相同的规律，返回 false；接着获取 pattern 中每个字符第一次出现的索引 和 list 中每个字符串第一次出现的索引，如果它们不同，则说明 pattern 和 s 不遵循相同的规律，返回 false；如果能比较完全部 字符 与 字符串 都不返回 false，那么说明 pattern 和 s 遵循相同的规律，返回 true。

代码

class Solution {
    public boolean wordPattern(String pattern, String s) {
        List<String> list = List.of(s.split(" ")); // 用 空格 分割，将 pattern 分割到一个 List 集合中
        int n = pattern.length(); // 获取 s 的长度
        if (n != list.size()) { // 如果 pattern中字符的个数 与 list中字符串的个数 不相同
            return false; // 则 pattern 和 s 不遵循相同的规律，返回 false
        }
        
        for (int i = 0; i < n; i++) { // 遍历比较每个 字符 与 字符串
            int pi = pattern.indexOf(pattern.charAt(i); // 获取 本字符 第一次出现的索引
            int si = list.indexOf(list.get(i)); // 获取 本字符串 第一次出现的索引
            if (pi != si) { // 如果 字符第一次出现的索引 与 字符串第一次出现的索引 不同
                return false; // 则 pattern 和 s 不遵循相同的规律，返回 false
            }
        }
        return true; // pattern 和 s 遵循相同的规律，返回 true
    }
}