LeetCode 290. 单词规律

约 4 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 面试经典 150 题 字节 阿里 美团
标签
字符串 哈希表

题目描述

✅ 290. 单词规律

image-20260928231207900

image-20260928231207903

题意分析

将句子按空格分成单词后，判断它与模式字符串是否具有相同规律：每个模式字符固定对应一个完整单词，不同字符不能对应同一个单词。

对应关系是一一映射，既要求同字符始终对应同词，也要求同词始终对应同字符。模式长度必须等于单词个数；题目保证单词之间用单个空格分隔，没有首尾空格。

解法：双向哈希映射

核心思路

[!blue]

先拆分单词并检查数量，只有位置能够逐一对应才继续。用 charToWord 保存字符到单词的关系，用 wordToChar 保存反向关系。

检查当前位置的字符与单词：如果字符已有记录，但此前对应的单词不同，则同一字符映射不一致；如果单词已有记录，但此前对应的字符不同，则两个字符争用了同一单词。任意一边冲突都应立即失败。

两边旧记录都一致或不存在时，才能成对写入当前关系。处理完每个位置后，映射恰好描述已扫描前缀，且保持双向唯一；后续继续使用这个不变量检查即可。

全部位置通过时，每一个配对都与此前保持一致，而且两个方向都没有冲突，因此已经建立要求的一一映射。仅检查不同字符和不同单词的种类数不能保证这种逐位置关系。

解题步骤

  1. 按空格切出单词，词数与模式长度不同则直接失败。
  2. 创建字符到词、词到字符两张空映射。
  3. 逐位置检查两边是否已有不一致的旧关系。
  4. 没有冲突就同时写入两个方向，继续检查下一位置。
  5. 全部通过返回 true。

代码实现

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");

        if (pattern.length() != words.length) {
            return false;
        }

        Map<Character, String> charToWord = new HashMap<>();
        Map<String, Character> wordToChar = new HashMap<>();

        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String word = words[i];

            if (charToWord.containsKey(c) && !charToWord.get(c).equals(word)) {
                return false;
            }

            // 反向映射排除两个不同字符共用同一个单词
            if (wordToChar.containsKey(word) && wordToChar.get(word) != c) {
                return false;
            }

            // 两个方向都检查通过后再写入，避免覆盖旧映射掩盖冲突
            charToWord.put(c, word);
            wordToChar.put(word, c);
        }

        return true;
    }
}

import "strings"

func wordPattern(pattern string, s string) bool {
    words := strings.Split(s, " ")
    if len(pattern) != len(words) {
        return false
    }

    charToWord := make(map[byte]string)
    wordToChar := make(map[string]byte)

    for i := 0; i < len(pattern); i++ {
        c := pattern[i]
        word := words[i]

        if mappedWord, ok := charToWord[c]; ok && mappedWord != word {
            return false
        }
        // 反向映射排除两个不同字符共用同一个单词
        if mappedChar, ok := wordToChar[word]; ok && mappedChar != c {
            return false
        }

        // 两个方向都检查通过后再写入，避免覆盖旧映射掩盖冲突
        charToWord[c] = word
        wordToChar[word] = c
    }

    return true
}

复杂度分析

  • 时间复杂度：期望 $O(S)$，其中 $S$ 为输入字符总数，包含切分、字符串哈希与内容比较。
  • 空间复杂度：$O(S)$，用于切分结果及映射记录。

关键点总结

[!green]

  • 双向约束分别防止“一字符多词”和“一词多字符”。
  • 先检查旧关系，再写入新关系，才能保留识别冲突的依据。
  • 比较的单位是整个单词，位置对应关系由模式字符逐一约束。

易错点总结

[!yellow]

  • 只维护字符到词，会允许不同字符复用同一个词，缺少反向唯一性。
  • 只维护词到字符，又可能让同一个字符对应多个词。
  • 先覆盖旧映射再检查，会把原来的冲突证据抹掉。
  • Java 单词内容使用 equals 比较，不能用引用是否相同替代。
  • 数量不同仍直接按位置遍历，可能漏掉额外单词或访问越界。

相似题目

题目 难度 关联与区别
205. 同构字符串 简单 同样检查双向一一映射，原题字符对字符，本题模式字符对应整个单词。
890. 查找和替换模式 中等 同样按首次出现关系验证同构模式，原题对多个候选词进行筛选。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/82761185
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！