290. 单词规律 Easy

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

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

示例 1：
输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2：
输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3：
输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

解题思路

输入：两个字符串 pattern 和 s

输出：判断 s 是否遵循相同的规律

本题属于 哈希表 问题。

用两个哈希表 keyMap valMap 记录 key -> val 以及 val -> key

将 s 拆分成数组 arr

以 pattern[i] 为 key，arr[i] 为 val

遍历字符串 s

• 判断 key 在 keyMap 时跟 arr 对应的字符是否一致
• 判断 val 在 valMap 时跟 pattern 对应的字符是否一致

然后记录在对应的哈希表中

都判断正确则返回正确

代码实现

python

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 将字符串 s 按空格切分成单词数组
        arr = s.split(' ')

        # 如果 pattern 的长度和单词数不同，肯定不符合规律
        if len(pattern) != len(arr):
            return False

        # 建立双向映射：
        # keyMap: pattern 字符 -> 单词
        # valMap: 单词 -> pattern 字符
        keyMap = {}
        valMap = {}

        # 遍历 pattern 和 arr
        for i in range(len(pattern)):
            key = pattern[i]  # 当前 pattern 字符
            val = arr[i]      # 当前单词

            # 如果 pattern 字符已出现过，但对应的单词不一致 ⇒ 冲突
            if key in keyMap and keyMap[key] != val:
                return False

            # 如果单词已出现过，但对应的 pattern 字符不一致 ⇒ 冲突
            if val in valMap and valMap[val] != key:
                return False

            # 建立/确认双向映射
            keyMap[key] = val
            valMap[val] = key

        # 遍历完毕没有冲突，说明符合规律
        return True

javascript

var wordPattern = function(pattern, s) {
    const arr = s.split(' ');

    if (pattern.length !== arr.length) return false;

    const keyMap = new Map;
    const valMap = new Map;

    for (let i = 0; i < pattern.length; i++) {
        const key = pattern[i];
        const val = arr[i];

        if (keyMap.has(key) && keyMap.get(key) !== val) return false;
        if (valMap.has(val) && valMap.get(val) !== key) return false;

        keyMap.set(key, val);
        valMap.set(val, key);
    }

    return true;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

290 国际版

290 中文版