LeetCode 面试题 16.18. 模式匹配

2023-10-12 HGNULB 约 14 分钟

文章信息 7 个分类 4 个标签

分类

LeetCode CodeTop 中等未解决 1-2 华为程序员面试金典（第 6 版）

题目描述

✅ 面试题 16.18. 模式匹配

题意分析

给定一个只由字符 a、b 组成的模式串 pattern 和一个只由小写字母组成的字符串 value，问是否存在一种映射：把 a 映射到某个字符串、把 b 映射到另一个字符串，使得按 pattern 的字符顺序把这些子串依次拼接起来，恰好等于 value。要求 a 和 b 映射到的字符串不能相同，但允许映射到空串。

约束里有三个决定性的信号。第一，模式串只有两种字符，所以未知量只有两个：a 对应子串的长度 lenA 和 b 对应子串的长度 lenB。第二，"可以映射到空串"——这条极其容易被忽略，它意味着 lenA 和 lenB 的取值下界是 0 而不是 1，pattern = "ab"、value = "a" 这种用例正是靠 a → ""、b → "a" 才成立。第三，"a 和 b 不能映射到同一个字符串"，这是唯一的额外约束，必须在验证时显式检查，且只在两种字符都出现时才有意义。

边界上要覆盖：value 为空串（此时只有 pattern 中仅含一种字符时才可能成立，因为两个都出现就必须互不相同，而都只能是空串）；pattern 为空而 value 非空（无论如何拼不出，返回 false）；pattern 中只有 a 或只有 b（另一个字符的长度无从约束，要单独处理）；以及 lenA、lenB 都为 0 的退化情形。

解法：枚举子串长度 + 线性验证

核心思路

暴力想法是枚举 a 和 b 各自映射到哪个子串，两层枚举起点和长度，规模是 $O(n^4)$ 量级，再乘上验证代价，完全不可行。

突破口在于一条长度守恒的等式。设 pattern 中 a 出现 countA 次、b 出现 countB 次，那么拼接结果的总长度必然满足：

\[countA \cdot lenA + countB \cdot lenB = |value|\]

这条等式把两个未知量绑成了一个：只要枚举 lenA，lenB 就被唯一确定（当 countB > 0 时 lenB = (|value| - countA \cdot lenA) / countB，且必须整除、必须非负）。于是搜索空间从二维塌成一维，lenA 的取值只有 $0$ 到 $ value / countA$ 这 $O(n)$ 种。

更关键的是，长度一旦确定，映射就完全确定了：按 pattern 从左到右扫描，遇到 a 就从 value 当前位置切下 lenA 个字符、遇到 b 就切下 lenB 个字符，切下来的第一个 a 段就是 a 的映射值，之后每个 a 段都必须与它相同；b 同理。所以验证是一次线性扫描，不需要任何回溯。

由此确定整体骨架：外层枚举 lenA（$O(n)$ 种），内层线性验证（$O(n)$），总复杂度 $O(n^2)$。验证函数 check(lenA, lenB) 维护的不变量是：扫描到 pattern 的第 i 个字符时，idx 恰好等于前 i 个字符消费掉的总长度，且 wordA/wordB 分别记录了目前为止见过的 a 段、b 段内容（若尚未出现则为未初始化）。任意一段与已记录的不一致，或者 wordA 与 wordB 相等，立刻返回 false。

两个特殊情形要单独交代。其一，countB == 0（模式里只有 a）：lenB 不受等式约束，取任何值都行，代码里固定取 0，并要求 rest == 0（即 countA * lenA 恰好等于总长）；此时 wordB 永远不会被赋值，那条"两者不能相同"的检查自然不会触发，符合题意——只有一种字符时没有"不同"的要求。其二，value 为空串：只要 pattern 中有任一种字符不出现，剩下那种映射到空串即可，返回 true；若两种字符都出现，它们就都只能是空串，违反"不能相同"，返回 false。这正是代码里 return countA == 0 || countB == 0; 那一行的含义。

解题步骤

先统计 countA 和 countB。这两个计数是长度等式的系数，也是后续所有分支判断的依据，必须在枚举之前一次算好。

处理 value 为空的边界，返回 countA == 0 || countB == 0。放在最前面是因为空串会让后面的"枚举长度"整段失去意义（n = 0 时 maxLenA = 0，逻辑虽然也能跑通但推理绕）。这一行同时覆盖了 pattern 也为空的情形（两个计数都是 0，返回 true）。

处理 pattern 为空而 value 非空，返回 false。空模式拼不出任何非空串。注意这条必须放在上一条之后，否则 pattern 和 value 都为空时会被误判成 false。

计算 maxLenA：countA == 0 时取 0（a 不出现，只需试 lenA = 0 这一种），否则取 n / countA——再大的话 countA * lenA 就超过总长度了。这个上界让外层循环的规模是 $O(n / countA)$，countA 越大枚举越少。

外层从 lenA = 0 枚举到 maxLenA，下界必须是 0，因为允许映射到空串。每轮先算 rest = n - lenA * countA，即留给所有 b 段的总长度。

countB == 0 时单独走一条分支：要求 rest == 0（a 段必须刚好铺满整个 value），然后用 lenB = 0 去验证。不能走下面的通用分支，因为那里要对 countB 做除法和取模，会除零。

通用分支里检查 rest < 0 || rest % countB != 0 就跳过。前者说明 a 段已经超长，后者说明剩余长度无法被 countB 等分，这个 lenA 不可能有解。这两条剪枝把绝大多数无效枚举挡在验证之外。

check(lenA, lenB) 里按 pattern 顺序切片比对。遇到 a 就切 lenA 长，第一次出现记录进 wordA，之后每次都与 wordA 比对；b 同理。每切一段之后立刻检查 wordA 与 wordB 是否都已赋值且相等，若是则返回 false——把这条检查放在循环内而不是循环末尾，可以尽早剪枝。

任意一次验证成功立刻返回 true，全部枚举完毕返回 false。

以 pattern = "abba"、value = "dogcatcatdog" 走一遍（n = 12，countA = 2，countB = 2，maxLenA = 6）：

lenA = 0：rest = 12，能被 2 整除，lenB = 6。验证：第一个字符 a 切下长度 0 的段 ""，记 wordA = ""；第二个字符 b 切下 value[0..6) = "dogcat"，记 wordB = "dogcat"，两者不同，继续；第三个字符 b 切下 value[6..12) = "catdog"，与 wordB 不符，返回 false。

lenA = 1：rest = 10，lenB = 5。a → "d"；b → value[1..6) = "ogcat"；下一个 b → value[6..11) = "catdo"，不符，false。

lenA = 2：rest = 8，lenB = 4。a → "do"；b → value[2..6) = "gcat"；下一个 b → value[6..10) = "catd"，不符，false。

lenA = 3：rest = 12 - 6 = 6，能被 2 整除，lenB = 3。验证：第一个 a 切下 value[0..3) = "dog"，记 wordA = "dog"；第一个 b 切下 value[3..6) = "cat"，记 wordB = "cat"，两者不同；第二个 b 切下 value[6..9) = "cat"，与 wordB 一致；第二个 a 切下 value[9..12) = "dog"，与 wordA 一致。扫描结束，idx = 12 恰好用完整个 value，返回 true。整体返回 true，映射为 a → "dog"、b → "cat"。

再以 pattern = "abba"、value = "dogcatcatfish" 走一遍（n = 13）：countA = countB = 2，maxLenA = 6。lenA = 0 时 rest = 13，13 % 2 != 0，跳过；lenA = 1 时 rest = 11，奇数跳过；lenA = 2 时 rest = 9，跳过；lenA = 3 时 rest = 7，跳过；lenA = 4 时 rest = 5，跳过；lenA = 5 时 rest = 3，跳过；lenA = 6 时 rest = 1，跳过。所有取值都被整除性剪掉，返回 false，正确。这个例子显示了取模剪枝的威力——连一次字符串比对都没做。

最后看 pattern = "aaaa"、value = "dogcatcatdog"：countA = 4，countB = 0，maxLenA = 3。lenA = 0 时 rest = 12 != 0，跳过；lenA = 1 时 rest = 8 != 0，跳过；lenA = 2 时 rest = 4 != 0，跳过；lenA = 3 时 rest = 0，进入验证：四个 a 段依次是 "dog"、"cat"、"cat"、"dog"，第二段与 wordA = "dog" 不符，返回 false。整体 false，正确。

代码实现

class Solution {
    public boolean patternMatching(String pattern, String value) {
        int countA = 0;
        int countB = 0;
        for (char c : pattern.toCharArray()) {
            if (c == 'a') {
                countA++;
            } else {
                countB++;
            }
        }

        if (value.isEmpty()) {
            return countA == 0 || countB == 0;
        }
        if (pattern.isEmpty()) {
            return false;
        }

        int n = value.length();

        int maxLenA = countA == 0 ? 0 : n / countA;
        for (int lenA = 0; lenA <= maxLenA; lenA++) {
            int rest = n - lenA * countA;
            if (countB == 0) {
                if (rest == 0 && check(pattern, value, lenA, 0)) {
                    return true;
                }
                continue;
            }
            if (rest < 0 || rest % countB != 0) {
                continue;
            }
            int lenB = rest / countB;
            if (check(pattern, value, lenA, lenB)) {
                return true;
            }
        }
        return false;
    }

    private boolean check(String pattern, String value, int lenA, int lenB) {
        int idx = 0;
        String wordA = null;
        String wordB = null;

        for (char c : pattern.toCharArray()) {
            int len = (c == 'a') ? lenA : lenB;
            String sub = value.substring(idx, idx + len);
            if (c == 'a') {
                if (wordA == null) {
                    wordA = sub;
                } else if (!wordA.equals(sub)) {
                    return false;
                }
            } else {
                if (wordB == null) {
                    wordB = sub;
                } else if (!wordB.equals(sub)) {
                    return false;
                }
            }
            if (wordA != null && wordB != null && wordA.equals(wordB)) {
                return false;
            }
            idx += len;
        }
        return true;
    }
}

func patternMatching(pattern string, value string) bool {
    countA, countB := 0, 0
    for _, c := range pattern {
        if c == 'a' {
            countA++
        } else {
            countB++
        }
    }

    if len(value) == 0 {
        return countA == 0 || countB == 0
    }
    if len(pattern) == 0 {
        return false
    }

    n := len(value)

    check := func(lenA, lenB int) bool {
        idx := 0
        wordA, wordB := "", ""
        hasA, hasB := false, false

        for _, c := range pattern {
            length := lenB
            if c == 'a' {
                length = lenA
            }
            sub := value[idx : idx+length]

            if c == 'a' {
                if !hasA {
                    wordA = sub
                    hasA = true
                } else if wordA != sub {
                    return false
                }
            } else {
                if !hasB {
                    wordB = sub
                    hasB = true
                } else if wordB != sub {
                    return false
                }
            }
            if hasA && hasB && wordA == wordB {
                return false
            }
            idx += length
        }
        return true
    }

    maxLenA := 0
    if countA > 0 {
        maxLenA = n / countA
    }
    for lenA := 0; lenA <= maxLenA; lenA++ {
        rest := n - lenA*countA
        if countB == 0 {
            if rest == 0 && check(lenA, 0) {
                return true
            }
            continue
        }
        if rest < 0 || rest%countB != 0 {
            continue
        }
        lenB := rest / countB
        if check(lenA, lenB) {
            return true
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n^2)$，n = |value|。外层枚举 lenA 最多 $n / countA + 1$ 次；每次验证要沿 pattern 切出 |pattern| 个子串，所有子串的总长度恰好是 n，所以单次验证是 $O(n)$。整除性剪枝在实践中能砍掉绝大部分枚举，但最坏情况（如 countB = 1）仍是平方级。

空间复杂度：$O(n)$。验证时用 substring/切片保存 wordA、wordB 和当前段，最长各为 $O(n)$；Go 的字符串切片是共享底层数组的视图，实际额外开销更小。若要做到 $O(1)$ 额外空间，可以改成"只记录每段的起始下标，比较时逐字符对比"，代价是代码变长。

关键点总结

多个未知量时，先找一条把它们绑起来的守恒等式。本题的 $countA \cdot lenA + countB \cdot lenB = value $ 把二维搜索压成一维枚举，这是整题的胜负手。凡是"若干段拼成一个整体"的题，长度守恒都值得第一时间写出来。

枚举出的候选要先用整除性/非负性剪枝，再进入昂贵的验证。取模和符号检查是 $O(1)$ 的，能在字符串比对之前挡掉大部分无效分支；先剪枝后验证是所有枚举类题目的通用节奏。

"可以为空"这类宽松条件必须落到枚举下界上。lenA 从 0 起枚举，是本题最容易漏掉的一行；把题面里每一条"允许 / 可以"都翻译成具体的取值范围，再写循环。

"两者不能相同"只在两者都出现时才有意义。用"是否已赋值"的标志来守卫这条检查（Java 靠 null、Go 靠 hasA/hasB），既避免了空串的误判，也让只含一种字符的模式自然通过。

退化情形（某个计数为 0）单独开分支，不要硬塞进通用公式。countB == 0 时通用分支会除零，countA == 0 时 maxLenA 的公式没有意义。设计枚举上界和分支时，先问一句"哪个量可能是 0"。

面试视角：先说等式再说枚举，最后主动交代边界清单。面试官考这题就是看你能否把"两个未知量"降到"一个"，以及能否把空串、单字符模式这些边界数清楚。开口顺序建议是：统计次数 → 写长度等式 → 说明枚举 lenA 即可 → 列出 value 为空、pattern 单字符两个特判 → 再写代码，这样即使代码没写完，思路分也拿满了。

易错点总结

错误写法：lenA 从 1 开始枚举 → 用例 pattern = "ab"、value = "a"：正确答案是 true（a → ""、b → "a"），但从 1 起枚举时 lenA = 1 得到 rest = 0、lenB = 0，此时 wordA = "a"、wordB = "" 不同，居然也返回 true；换成 pattern = "aab"、value = "b" 就会漏解返回 false（正解是 a → ""、b → "b"）。允许空串就必须从 0 起枚举。

错误写法：漏掉 wordA.equals(wordB) 的检查 → 用例 pattern = "ab"、value = "aa"：lenA = 1、lenB = 1 时两段都是 "a"，被判为匹配返回 true，正确答案是 false——a 和 b 不能映射到同一个字符串。

错误写法：无条件检查 wordA.equals(wordB)，不判断两者是否都已出现 → 用例 pattern = "aa"、value = "aa"：wordB 始终是初始值（若初始化成 "" 而非 null），而 lenA = 1 时 wordA = "a" 与 "" 不等尚可；但用例 pattern = "aa"、value = "" 下 wordA = "" 与 wordB = "" 相等被误判为 false，正确答案是 true。守卫标志不可省。

错误写法：countB == 0 时不单独分支，直接算 rest % countB → 用例 pattern = "aaaa"、value = "dogcatcatdog"：除零，Java 抛 ArithmeticException，Go 直接 panic。

错误写法：countB == 0 分支里不检查 rest == 0 → 用例 pattern = "aa"、value = "abc"：lenA = 1 时 rest = 1，若直接拿 lenB = 0 去验证，切完两个 a 段后 idx = 2，value 还剩一个字符没被消费却返回了 true，正确答案是 false。只有 a 段时必须刚好铺满。

错误写法：两个空串特判的顺序写反，先判 pattern.isEmpty() 返回 false → 用例 pattern = ""、value = ""：被判成 false，正确答案是 true（空模式拼出空串是成立的）。

错误写法：value 为空时返回 true → 用例 pattern = "ab"、value = ""：a 和 b 都只能是空串，违反"不能相同"，正确答案是 false。必须写成 countA == 0 || countB == 0。

错误写法：maxLenA 写成 n（不除以 countA） → 用例 pattern = "aab"、value 长度 100：lenA 取到 60 时 rest = 100 - 120 = -20，若又漏掉 rest < 0 的检查，lenB 会算成负数，value.substring(idx, idx + len) 传入负长度直接抛异常。上界和负值检查至少要留一个。

错误写法：验证时用 value.indexOf 之类的查找代替按位置切片 → 用例 pattern = "abba"、value = "dogcatcatdog"：查找会跳到第一个匹配处而不是当前应有的位置，idx 与实际消费长度脱节，"catdog" 这种跨段的巧合会导致误判。切片位置必须由累计长度 idx 严格决定。

错误写法：Go 里把 wordA、wordB 初始化成 "" 并用 wordA == "" 判断"是否已出现" → 用例 pattern = "aab"、value = "b"：lenA = 0 时第一个 a 段就是空串，程序误以为"还没出现过 a"，第二段又被当成首次赋值，重复比较的约束整个失效。必须用独立的布尔标志。

错误写法：check 里遍历 pattern 用 for i, c := range pattern 并把 i 当作消费位置 → 用例任意：range 给出的是 pattern 里的字节偏移，与 value 的消费进度毫无关系。消费位置必须用单独的 idx 累加各段长度。

错误写法：验证成功后不立即返回，继续枚举并用某个变量累积结果 → 用例 pattern = "abba"、value = "dogcatcatdog"：lenA = 3 时已成立，若继续枚举到 lenA = 6 得到 rest = 0、lenB = 0，此时 wordA = "dogcat"、wordB = "" 也可能被判成立或不成立，取决于累积方式；一旦用"最后一次结果"覆盖，正确答案会被抹掉。存在性问题应当一命中就返回。

相似题目

题目	难度	考察点
290. 单词规律	简单	分割位置由空格给定，只需建双向映射校验一一对应
205. 同构字符串	简单	映射粒度是单字符，长度天然相等，重点是双向映射不能冲突
44. 通配符匹配	困难	`*` 可匹配任意长度但不要求各处一致，用动态规划而非枚举长度
10. 正则表达式匹配	困难	`*` 作用于前一字符，状态转移分"用零次"和"多用一次"两支
459. 重复的子字符串	简单	同样靠长度整除性枚举周期，但只有一个未知量且无需字符映射