当前位置:首页 > 力扣 > 力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配)

力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配)

2个月前 (07-07)

力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配) 模式匹配 动态规划 字符串匹配 算法优化 力扣面试题 第1张

一、题目解读

力扣面试16.18题要求判断字符串value是否可通过替换模式串pattern中的字符"a"和"b"(任意非空子串)进行匹配。例如,模式"aab"可匹配"xxxy",但无法匹配"xyx"。题目需高效算法判断匹配关系,涉及字符串处理动态规划思想。

二、解题思路

采用统计+枚举策略:

1. 统计字符数量:计算pattern中a、b出现次数,确保a为多数字符(通过交换优化后续处理)。

2. 空值处理:若value为空,仅当pattern全a或全b时才匹配。

3. 枚举a的长度:遍历a的可能子串长度,计算剩余字符是否可被b均分。

4. 匹配验证:通过滑动窗口逐字符匹配,确保同一字母对应的子串一致。

三、解题步骤

1. 预处理:统计a、b数量并交换,使a占多数,减少分支讨论。

2. 处理空值:快速判断value为空的特例。

3. 枚举长度:从0到value长度除以a次数,计算b子串长度(或0)。

4. 匹配验证:使用双指针分别构建value_a和value_b子串,若发现不一致则终止。

四、代码与注释

class Solution {
public:
    bool patternMatching(string pattern, string value) {
        // 统计pattern中a和b的数量
        int count_a = 0, count_b = 0;
        for (char c : pattern) {
            if (c == 'a') count_a++;
            else count_b++;
        }
        
        // 确保a是出现次数较多的字符,简化后续处理
        if (count_a < count_b) {
            swap(count_a, count_b);
            for (char& c : pattern) {
                c = (c == 'a')? 'b' : 'a'; // 交换a和b
            }
        }
        
        // 处理value为空的情况
        if (value.empty()) {
            return count_b == 0; // 只有全a或全b的模式可以匹配空字符串
        }
        
        // 枚举a可能的长度
        for (int len_a = 0; len_a <= value.size() / count_a; ++len_a) {
            int remaining = value.size() - count_a * len_a;
            // 检查b的长度是否有效
            if ((count_b == 0 && remaining == 0) || 
                (count_b!= 0 && remaining % count_b == 0)) {
                int len_b = (count_b == 0)? 0 : remaining / count_b;
                
                // 尝试匹配
                int pos = 0;
                string value_a, value_b;
                bool match = true;
                
                for (char c : pattern) {
                    if (c == 'a') {
                        string sub = value.substr(pos, len_a);
                        if (value_a.empty()) {
                            value_a = sub; // 记录第一个a对应的子串
                        } else if (value_a!= sub) { // 后续不一致则失败
                            match = false;
                            break;
                        }
                        pos += len_a;
                    } else {
                        string sub = value.substr(pos, len_b);
                        if (value_b.empty()) {
                            value_b = sub;
                        } else if (value_b!= sub) {
                            match = false;
                            break;
                        }
                        pos += len_b;
                    }
                }
                if (match && pos == value.size()) return true; // 完全匹配成功
            }
        }
        return false;
    }
};

五、总结

该解法通过统计与枚举结合,巧妙利用字符数量关系减少搜索空间。关键点在于:

1. 交换a、b确保主字符更易处理;

2. 空值特判避免后续逻辑复杂;

3. 滑动窗口匹配子串的一致性。

此思路对字符串匹配类问题具有通用性,体现了动态规划中“状态压缩”与“边界优化”的精髓。

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣746:三步通关最小花费爬楼梯

力扣746:三步通关最小花费爬楼梯

题目解析:站在楼梯的某个台阶时,需要支付当前台阶对应的体力值cost[i],之后可以选择向上爬1或2个台阶。最终目标是到达‌楼层顶部‌(即数组末尾之后的位置),且初始位置可选择下标0或1的台阶作为起点...

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

题目重解给定一个由数字组成的三角形结构,从顶部出发,每次可以移动到下方相邻的数字,最终到达底部。我们的目标是找到一条路径,使得路径上经过的数字总和最大。这个问题在实际中有许多应用场景,如最优路径规划、...

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。