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

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

3天前

力扣面试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. 滑动窗口匹配子串的一致性。

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

原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

力扣5:中心扩散法 轻松破解最长回文子串

力扣5:中心扩散法 轻松破解最长回文子串

题目解读:在一个给定的字符串中,我们需要找到最长的回文子串。回文是指正读反读都相同的字符串,如"aba"、"abba"都是回文。这个问题看似简单,但要在字符串中...

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

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

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

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

发表评论

访客

看不清,换一张

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