LeetCode 290. 单词规律：多种解法与性能对比

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

解法二：首次位置映射法

解题思路

核心方法：首次出现位置统一映射法，将'字符→单词'的双向映射转化为'字符/单词的首次出现位置'比对，用数组记录字符的首次位置、HashMap 记录单词的首次位置，通过'位置是否一致'判断是否满足规律，减少映射维护的开销，内存效率大幅提升。

核心逻辑拆解

规律匹配的本质是'字符和单词的出现模式完全一致'，比如：

• pattern="abba" 的首次出现位置：a(1)、b(2)、b(2)、a(1)；
• s="dog cat cat dog" 的首次出现位置：dog(1)、cat(2)、cat(2)、dog(1)；
• 位置序列完全一致则满足规律。

具体步骤：

1. 前置校验：分割 s 为单词数组，长度不一致直接返回 false；
2. 位置记录容器：
   • sPos 数组（长度 256）：记录 pattern 中每个字符的首次出现位置（字符 ASCII 码为下标，初始值 0）；
   • mapPos HashMap：记录 s 中每个单词的首次出现位置（初始无记录时返回 0）；
3. 遍历比对：
   • 取当前 pattern 字符 pc 和 s 单词 sc；
   • 若 pc 的首次位置（sPos[pc]）与 sc 的首次位置（mapPos.getOrDefault(sc,0)）不一致，返回 false；
   • 若一致，更新两者的首次位置为 i+1（避免与初始值 0 冲突）；
4. 遍历完成返回 true。

性能优化点

• 时间复杂度：仍为 O(n)，但减少了 HashMap 的'存值/取值'比对操作，仅需比对位置数值；
• 空间复杂度：O(k)（k 为不同单词数），但数组替代了一个 HashMap，内存开销降低；
• 核心优势：无需维护双向映射关系，仅通过'位置一致性'判断，逻辑更简洁，减少了 Map 的 equals 比对开销。

public boolean wordPattern(String pattern, String s) {
    String[] sArray = s.split(" ");
    if (pattern.length() != sArray.length) {
        return false;
    }
    int n = sArray.length;
    // 记录字符首次出现的位置（初始为 0）
    int[] sPos = new int[256];
    Map<String, Integer> mapPos = new HashMap<>();
    for (int i = 0; i < n; i++) {
        char pc = pattern.charAt(i);
        String sc = sArray[i];
        // 首次出现位置不同则不同构
        if (sPos[pc] != mapPos.getOrDefault(sc, 0)) {
            return false;
        }
        // 更新首次出现位置为 i+1（避免与初始值 0 冲突）
        sPos[pc] = i + 1;
        mapPos.put(sc, i + 1);
    }
    return true;
}

解法三：纯数组优化版

解题思路

核心方法：单词→数字编码 + 数组映射，先将 s 的单词映射为数字（如第一个单词→1，第二个新单词→2），再用两个数组分别记录 pattern 字符和 s 单词的编码，通过编码一致性判断规律，完全避免 HashMap 的使用，性能达到最优。

核心逻辑

1. 分割 s 为单词数组，长度不一致返回 false；
2. 用 wordToCode HashMap 将单词映射为唯一数字编码（仅用于临时编码）；
3. 初始化两个数组 patternCode（长度 300）、wordCode（长度 300）；
4. 遍历过程：
   • 对每个单词，若未编码则分配递增编码（从 1 开始）；
   • 将 pattern 字符转为编码（如 'a'→0, 'b'→1）；
   • 记录 pattern 字符编码和单词编码到对应数组；
   • 若两者编码不一致，返回 false；
5. 遍历完成返回 true。

代码实现

public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) {
        return false;
    }
    int n = pattern.length();
    // 单词→数字编码（避免重复单词）
    Map<String, Integer> wordToCode = new HashMap<>();
    int[] patternCode = new int[n];
    int[] wordCodeArr = new int[n];
    int code = 1;
    for (int i = 0; i < n; i++) {
        // pattern 字符编码（a→0, b→1...）
        patternCode[i] = pattern.charAt(i) - 'a';
        // 单词编码（首次出现分配新编码）
        String word = words[i];
        if (!wordToCode.containsKey(word)) {
            wordToCode.put(word, code++);
        }
        wordCodeArr[i] = wordToCode.get(word);
        // 编码不一致则不满足规律
        if (patternCode[i] != wordCodeArr[i] - 1) {
            // 对齐编码起始值
            return false;
        }
    }
    return true;
}

优势说明

• 时间复杂度：O(n)，HashMap 仅用于单词编码，且仅做'是否存在'判断，开销极小；
• 空间复杂度：O(k)（k 为不同单词数），数组访问速度远超 HashMap；
• 极致性能：完全基于数组比对，无字符串 equals 操作，是大数据量下的最优选择。

解法四：无分割优化版

解题思路

核心方法：遍历字符串不分割，通过双指针直接遍历 s 的单词（避免分割生成单词数组），进一步降低内存开销，适合 s 长度极大的场景。

代码实现

public boolean wordPattern(String pattern, String s) {
    int pLen = pattern.length();
    int sLen = s.length();
    int pIdx = 0, sIdx = 0;
    Map<Character, String> charToWord = new HashMap<>();
    Map<String, Character> wordToChar = new HashMap<>();
    while (pIdx < pLen && sIdx < sLen) {
        // 取 pattern 当前字符
        char c = pattern.charAt(pIdx);
        // 双指针找当前单词的结束位置
        int end = sIdx;
        while (end < sLen && s.charAt(end) != ' ') {
            end++;
        }
        String word = s.substring(sIdx, end);
        sIdx = end + 1;
        // 移动到下一个单词起始位置
        // 双向映射校验
        if (charToWord.containsKey(c)) {
            if (!charToWord.get(c).equals(word)) {
                return false;
            }
        } else {
            if (wordToChar.containsKey(word)) {
                return false;
            }
            charToWord.put(c, word);
            wordToChar.put(word, c);
        }
        pIdx++;
    }
    // 校验是否都遍历完成（避免 pattern 遍历完但 s 还有单词，或反之）
    return pIdx == pLen && sIdx > sLen;
}

优势说明

• 内存优化：无需生成单词数组，直接遍历字符串截取单词，节省数组存储的内存；
• 提前终止：遍历过程中若发现不匹配可立即终止，无需分割整个字符串；
• 适用场景：s 长度极大（如接近 3000）时，避免分割生成大数组，内存效率更高。

总结

1. 双向哈希表法：逻辑直观，清晰体现'一一对应'约束，适合新手理解核心原理；
2. 首次位置映射法：减少 Map 比对开销，内存效率更高，是平衡性能和可读性的优选；
3. 纯数组优化版：极致性能，无字符串 equals 操作，适合大数据量场景；
4. 无分割优化版：减少内存开销，避免生成单词数组，适合超长字符串场景；
5. 关键技巧：
   • 前置校验（长度一致）是必做步骤，可快速过滤无效用例；
   • 字符类映射优先用数组（ASCII 范围）替代 HashMap，提升性能；
   • 避免不必要的字符串操作（如分割、equals），可大幅降低内存/时间开销。