当前位置:首页 > 力扣 > 力扣面试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. 滑动窗口匹配子串的一致性。

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

原创内容 转载请注明出处

分享给朋友:

相关文章

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

牛客DP41精讲:当背包必须装满时,你的状态转移方程该如何调整?

题目重解我们面对一个经典背包问题的变体:给定n个物品,每个物品有重量w和价值v,背包容量为V。需要回答两个问题:1) 普通情况下能获得的最大价值;2) 必须恰好装满背包时的最大价值(若无法装满则输出0...

从零到一掌握背包问题:洛谷P1164题解精讲,附带优化

从零到一掌握背包问题:洛谷P1164题解精讲,附带优化

题目重解:小A带着m元钱来到餐馆,菜单上有n道菜,每道菜都有确定的价格。现在需要计算出刚好花完m元的点菜方案总数。这个问题看似简单,但当菜品数量增多时,暴力枚举就会变得不可行,需要更高效的算法来解决。...

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

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

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

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

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

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

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂...

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

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

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

发表评论

访客

看不清,换一张

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