LeetCode 面试题 16.18. 模式匹配

Categories:

题目描述
思路分析
1. 解法一：枚举 + 数学验证（推荐）
相似题目

题目描述

✅ 面试题 16.18. 模式匹配

思路分析

解法一：枚举 + 数学验证（推荐）

核心思路：

模式串由 a 和 b 两种字符组成，设 a 出现 countA 次，b 出现 countB 次

枚举 a 对应子串的长度 lenA（从 0 到 value.length / countA），通过数学推导得到 lenB

验证：按模式串顺序拼接，检验是否等于 value

特殊情况：若 countA == 0 或 countB == 0，只需验证另一种字符对应的子串是否能整除 value

复杂度分析：

时间复杂度：O(n²)，其中 n 表示 value 的长度，枚举 lenA 最多 n 次，每次验证 O(n)

空间复杂度：O(n)，用于存储子串

class Solution {
    public boolean patternMatching(String pattern, String value) {
        int countA = 0;
        int countB = 0;

        // 统计模式串中 a、b 的数量
        for (char c : pattern.toCharArray()) {
            if (c == 'a') {
                countA++;
            } else {
                countB++;
            }
        }

        // 若 value 为空，模式串必须全为同一种字符或为空
        if (value.isEmpty()) {
            return countA == 0 || countB == 0;
        }

        // 若模式串为空，value 也必须为空
        if (pattern.isEmpty()) {
            return false;
        }

        int n = value.length();

        // 枚举 a 对应子串的长度
        for (int lenA = 0; lenA * countA <= n; lenA++) {
            int rest = n - lenA * countA;

            // b 的子串长度必须能整除 rest
            if (countB == 0) {
                if (rest == 0 && check(pattern, value, lenA, 0)) {
                    return true;
                }
            } else if (rest % countB == 0) {
                int lenB = rest / countB;
                if (check(pattern, value, lenA, lenB)) {
                    return true;
                }
            }
        }

        return false;
    }

    // 按模式串拼接，验证是否与 value 相等
    private boolean check(String pattern, String value, int lenA, int lenB) {
        int index = 0;
        String wordA = null;
        String wordB = null;

        for (char c : pattern.toCharArray()) {
            int len = (c == 'a') ? lenA : lenB;
            String sub = value.substring(index, index + 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;
                }
            }

            // 确保 a 和 b 对应的子串不同（若两者长度相同）
            if (wordA != null && wordB != null && wordA.equals(wordB)) {
                return false;
            }

            index += len;
        }

        return true;
    }
}

func patternMatching(pattern string, value string) bool {
    countA, countB := 0, 0

    // 统计模式串中 a、b 的数量
    for _, c := range pattern {
        if c == 'a' {
            countA++
        } else {
            countB++
        }
    }

    // 若 value 为空，模式串必须全为同一种字符或为空
    if len(value) == 0 {
        return countA == 0 || countB == 0
    }

    // 若模式串为空，value 也必须为空
    if len(pattern) == 0 {
        return false
    }

    n := len(value)

    // 按模式串拼接，验证是否与 value 相等
    check := func(lenA, lenB int) bool {
        index := 0
        wordA, wordB := "", ""
        hasA, hasB := false, false

        for _, c := range pattern {
            var length int
            if c == 'a' {
                length = lenA
            } else {
                length = lenB
            }

            sub := value[index : index+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
                }
            }

            // 确保 a 和 b 对应的子串不同
            if hasA && hasB && wordA == wordB {
                return false
            }

            index += length
        }

        return true
    }

    // 枚举 a 对应子串的长度
    for lenA := 0; lenA*countA <= n; lenA++ {
        rest := n - lenA*countA

        if countB == 0 {
            if rest == 0 && check(lenA, 0) {
                return true
            }
        } else if rest%countB == 0 {
            lenB := rest / countB
            if check(lenA, lenB) {
                return true
            }
        }
    }

    return false
}

相似题目

题目	难度	考察点
10. 正则表达式匹配	困难	动态规划、字符串匹配
44. 通配符匹配	困难	动态规划、字符串匹配
28. 找出字符串中第一个匹配项的下标	简单	字符串、KMP
291. 单词规律 II	中等	回溯、哈希表
290. 单词规律	简单	哈希表、字符串
205. 同构字符串	简单	哈希表、字符串

本文作者: HGNULB

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