LeetCode 面试题 16.18. 模式匹配

2023-10-12 HGNULB 约 8 分钟

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

分类

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

题目描述

✅ 面试题 16.18. 模式匹配

题意分析

模式只含 a、b，每种字符对应一个固定字符串，将它们按模式顺序拼接后必须等于 value。映射可以为空，但两种字符都出现时不能对应同一个字符串；同一种字符重复出现，必须始终使用相同内容。

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

核心思路

[!blue]

设两种字符出现次数为 countA、countB，映射长度为 lenA、lenB，值串长度为 N。任何合法方案都满足 countA * lenA + countB * lenB = N。因此只需枚举 lenA：当 countA > 0 时范围是 0..N/countA；当没有 a 时，令 lenA = 0 即可，不必枚举一个未使用的长度。

固定 lenA 后，令 rest = N - countA * lenA。如果存在 b，只有 rest 能被 countB 整除时才有候选，且 lenB 唯一等于这个商；没有 b 时，则必须让 rest = 0，不能作除法。这覆盖了所有可能的长度组合。

长度确定后，字符串内容也不需要另行枚举：用游标 idx 按模式从左到右切片，某种字符首次出现时，对应片段就是它必须映射的字符串，之后每次都与首次片段比较。出现内容不一致，或两种已出现映射相同，就排除这组长度；全部通过则得到合法方案。长度等式已经保证总消费量恰好为 N，且每段长度非负，所以切片不会超过末尾。

空串要先处理：value 为空时，模式中出现的每种字符都只能映射为空；两种都出现便违反映射不同的要求，只出现一种或模式也为空则可行。value 非空而模式为空时无法生成任何字符，应返回 false。

解题步骤

统计 countA、countB，先处理空值串和空模式。

从零开始枚举 lenA，根据剩余长度和 countB 确定 lenB，跳过不能满足长度等式的候选。

验证时从 idx = 0 开始，按当前模式字符对应的长度取片段，首次保存、以后比较，并推进游标。

两种映射都已确定后，检查它们不能相等。Java 用 null 区分未出现，Go 用 hasA、hasB，不能把空字符串直接当作未初始化标记。

任一候选通过就返回 true，所有长度都失败才返回 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
}

复杂度分析

设模式长度为 P、值串长度为 N、枚举的长度候选数为 M。有 a 时 M = N/countA + 1，没有 a 时为 1。

时间复杂度：上界为 $O(P+M(P+N+1))$。每个候选最多遍历整个模式，并切分、比较总长为线性级别的字符串片段；即使片段为空，仍需扫描模式字符。

空间复杂度：Java 验证会创建模式字符数组和子串副本，上界为 $O(P+N)$；Go 仅保存字符串切片和标量，辅助空间为 $O(1)$。

关键点总结

[!green]

长度等式消掉一个枚举维度，首次出现的片段又确定了映射内容。

合法性同时要求总长度吻合、同字符内容一致、两种已出现映射不同。

空映射是一种合法取值，与“这个字符尚未出现”是两种状态。

易错点总结

[!yellow]

枚举从 1 开始，会漏掉某一种映射为空的合法方案。

只验证长度不验证片段内容，无法保证同一模式字符始终表示同一个字符串。

两种映射都出现后必须检查不同，不能仅凭拼接结果相同就接受。

某种字符出现次数为零时需要单独处理，不能把零作为除数。

值串游标按片段长度推进，不是每处理一个模式字符就只增加 1。

相似题目

题目	难度	关联与区别
290. 单词规律	简单	原题单词边界由空格给出，本题未知映射子串长度，需要枚举并验证拼接。
291. 单词规律 II	中等	原题模式字符更多且映射非空，本题只有a、b并允许空串，长度枚举的起点与约束不同。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/66038056

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！