动态规划--通配字符串匹配

这篇具有很好参考价值的文章主要介绍了动态规划--通配字符串匹配。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 题目来源
链接:通配符匹配
来源:LeetCode

2. 题目说明
给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。
示例1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例2:

输入:
s = “aa”
p = ""
输出: true
解释: '’ 可以匹配任意字符串。

示例3:

输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

示例4:

输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘’ 可以匹配空字符串, 第二个 '’ 可以匹配字符串 “dce”.

示例5:

输入:
s = “acdcb”
p = “a*c?b”
输入: false

题目解析

方法一:

朴素遍历解法、考虑条件繁多
这道题通配符匹配问题还是小有难度的,有特殊字符 ‘ * ’ 和 ‘?’,其中 ‘?’ 能代替任何字符,‘*’ 能代替任何字符串。这道题最大的难点,就是对于星号的处理,可以匹配任意字符串,简直像开了挂一样,有以下几点:

在星号对应位置之前,不管你s中有任何字符串,我大星号都能匹配你,主角光环啊。
但即便叼如斯的星号,也有其处理不了的问题,那就是一旦p中有s中不存在的字符,那么一定无法匹配,因为星号只能增加字符,不能消除字符。
再有就是星号一旦确定了要匹配的字符串,对于星号位置后面的匹配情况也就鞭长莫及了。
所以p串中星号的位置很重要,用 jStar 来表示,还有星号匹配到s串中的位置,使用 iStart 来表示,这里 iStar 和 jStar 均初始化为 -1,表示默认情况下是没有星号的。然后再用两个变量i和j分别指向当前s串和p串中遍历到的位置。

开始进行匹配:

若i小于s串的长度,进行 while 循环。
若当前两个字符相等,或着p中的字符是问号,则i和j分别加1。
若 p[j] 是星号,要记录星号的位置,jStar 赋为j,此时j再自增1,iStar 赋为i。
若当前 p[j] 不是星号,并且不能跟 p[i] 匹配上,此时就要靠星号了,若之前星号没出现过,那么就直接跪,比如 s = “aa” 和 p = “c*”,此时 s[0] 和 p[0] 无法匹配,虽然 p[1] 是星号,但还是跪。如果星号之前出现过,可以强行续一波命,比如 s = “aa” 和 p = “*c”,当发现 s[1] 和 p[1] 无法匹配时,但是好在之前 p[0] 出现了星号,把 s[1] 交给 p[0] 的星号去匹配。至于如何知道之前有没有星号,这时就能看出 iStar 的作用了,因为其初始化为 -1,而遇到星号时,其就会被更新为i,只要检测 iStar 的值,就能知道是否可以使用星号续命。
虽然成功续了命,匹配完了s中的所有字符,但是之后还要检查p串,此时没匹配完的p串里只能剩星号,不能有其他的字符,将连续的星号过滤掉,如果j不等于p的长度,则返回 false,参见代码如下:
// 执行用时 :8 ms, 在所有 C++ 提交中击败了94.73%的用户
// 内存消耗 :9.1 MB, 在所有 C++ 提交中击败了78.21%的用户
class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, iStar = -1, jStar = -1, m = s.size(), n = p.size();
        while (i < m) {
            if (j < n && (s[i] == p[j] || p[j] == '?')) {
                ++i; ++j;
            } else if (j < n && p[j] == '*') {
                iStar = i;
                jStar = j++;
            } else if (iStar >= 0) {
                i = ++iStar;
                j = jStar + 1;
            } else return false;
        }
        while (j < n && p[j] == '*') ++j;
        return j == n;
    }
};

方法二:动态规划解法


这道题也能用动态规划来解,外卡匹配中的星号跟前面的字符没有半毛钱关系,如果前面的字符没有匹配上,那么直接返回 false 了,根本不用管星号。而星号存在的作用是可以表示任意的字符串,当然只是当匹配字符串缺少一些字符的时候起作用,当匹配字符串p包含目标字符串s中没有的字符时,将无法成功匹配。

对于这种玩字符串的题目,动态规划是一大神器,因为字符串跟其子串之间的关系十分密切,正好适合 DP 这种靠推导状态转移方程的特性。

那么先来定义dp数组吧,使用一个二维 dp 数组,其中 dp[i][j] 表示 s中前 i 个字符组成的子串和 p 中前 j 个字符组成的子串是否能匹配。大小初始化为 (m+1) x (n+1),加1的原因是要包含 dp[0][0] 的情况,因为若s和p都为空的话,也应该返回 true,所以也要初始化 dp[0][0] 为 true。还需要提前处理的一种情况是,当s为空,p为连续的星号时的情况。由于星号是可以代表空串的,所以只要s为空,那么连续的星号的位置都应该为 true,所以先将连续星号的位置都赋为 true。

然后就是推导一般的状态转移方程,如何更新 dp[i][j],首先处理比较 tricky 的情况:

若p中第j个字符是星号,由于星号可以匹配空串,所以如果p中的前 j-1 个字符跟s中前i个字符匹配成功了( dp[i][j-1] 为true)的话,则 dp[i][j] 也能为 true。或者若p中的前j个字符跟s中的前i-1个字符匹配成功了( dp[i-1][j] 为true )的话,则 dp[i][j] 也能为 true(因为星号可以匹配任意字符串,再多加一个任意字符也没问题)。
若p中的第j个字符不是星号,对于一般情况,假设已经知道了s中前 i-1 个字符和p中前 j-1 个字符的匹配情况(即 dp[i-1][j-1] ),现在只需要匹配s中的第i个字符跟p中的第j个字符,若二者相等( s[i-1] == p[j-1] ),或者p中的第j个字符是问号( p[j-1] == ‘?’ ),再与上 dp[i-1][j-1] 的值,就可以更新 dp[i][j] 了,参见代码如下:
// 执行用时 :116 ms, 在所有 C++ 提交中击败了43.78%的用户
// 内存消耗 :13.8 MB, 在所有 C++ 提交中击败了21.35%的用户
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};

方法三:递归解法、剪枝


其实这道题也可以使用递归来做,因为子串或者子数组这种形式,天然适合利用递归来做。但是愣了吧唧的递归跟暴力搜索并没有啥太大的区别,很容易被 OJ 毙掉 ,参见代码一:,有以下逐步优化的思路:

首先判断s串,若为空,那么再看p串,若p为空,则为 true,或者跳过星号,继续调用递归。若s串不为空,且p串为空,则直接 false。若s串和p串均不为空,进行第一个字符的匹配,若相等,或者 p[0] 是问号,则跳过首字符,对后面的子串调用递归。若 p[0] 是星号,先尝试跳过s串的首字符,调用递归,若递归返回 true,则当前返回 true。否则尝试跳过p串的首字符,调用递归,若递归返回 true,则当前返回 true。但是很不幸,内存超出限制了 MLE。做了简单的优化,跳过了连续的星号,但是这次时间超出了限制 TLE,参见代码二。思考想是不是取子串 substr() 操作太费时间,且调用递归的适合s串和p串又分别建立了副本,才导致的 TLE。于是想着用坐标变量来代替取子串,并且递归函数调用的s串和p串都加上引用,但尼玛还是跪了。参见代码三
找到一种神奇的剪枝的方法,这种解法的递归函数返回类型不是 bool 型,而是整型,有三种不同的状态,返回0表示匹配到了s串的末尾,但是未匹配成功;返回1表示未匹配到s串的末尾就失败了;返回2表示成功匹配。那么只有返回值大于1,才表示成功匹配。至于为何失败的情况要分类,就是为了进行剪枝。在递归函数中,若s串和p串都匹配完成了,返回状态2。若s串匹配完成了,但p串但当前字符不是星号,返回状态0。若s串未匹配完,p串匹配完了,返回状态1。若s串和p串均为匹配完,且当前字符成功匹配的话,对下一个位置调用递归。否则若p串当前字符是星号,首先跳过连续的星号。然后分别让星号匹配空串,一个字符,两个字符,…,直到匹配完整个s串,对每种情况分别调用递归函数,接下来就是最大的亮点了,也是最有用的剪枝,当前返回值为状态0或者2的时候,返回,否则继续遍历。如果仅仅是状态2的时候才返回,会有大量的重复计算,因为当返回值为状态0的时候,已经没有继续循环下去的必要了,非常重要的一刀剪枝,参见代码四如下:
代码一:

// 超出时间限制
class Solution {
public:
    bool isMatch(string s, string p) {
        if (s.empty()) return p.empty() || (p[0] == '*' && isMatch(s, p.substr(1)));
        if (p.empty()) return false;
        if (s[0] == p[0] || p[0] == '?') return isMatch(s.substr(1), p.substr(1));
        if (p[0] == '*') {
            if (isMatch(s.substr(1), p)) return true;
            if (isMatch(s, p.substr(1))) return true;
        }
        return false;
    }
};
代码二:

// 超出时间限制
class Solution {
public:
    bool isMatch(string s, string p) {
        if (s.empty()) return p.empty() || (p[0] == '*' && isMatch(s, p.substr(1)));
        if (p.empty()) return false;
        if (s[0] == p[0] || p[0] == '?') return isMatch(s.substr(1), p.substr(1));
        if (p[0] == '*') {
            if (isMatch(s.substr(1), p)) return true;
            int i = 0;
            while (i < p.size() && p[i] == '*') ++i;
            if (isMatch(s, p.substr(i))) return true;
        }
        return false;
    }
};
代码三:

// 超出时间限制
class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0);
    }
    bool helper(string& s, string& p, int i, int j) {
        if (i == s.size()) return j == p.size() || (p[j] == '*' && helper(s, p, i, j + 1));
        if (j == p.size()) return false;
        if (s[i] == p[j] || p[j] == '?') {
            return helper(s, p, i + 1, j + 1);
        }
        if (p[j] == '*') {
            if (helper(s, p, i + 1, j)) return true;
            while (j < p.size() && p[j] == '*') ++j;
            if (helper(s, p, i, j)) return true;
 
        }
        return false;
    }
};
代码四:

// 执行用时 :12 ms, 在所有 C++ 提交中击败了86.70%的用户
// 内存消耗 :9.2 MB, 在所有 C++ 提交中击败了77.99%的用户
class Solution {
public:
    bool isMatch(string s, string p) {
        return helper(s, p, 0, 0) > 1;
    }
    int helper(string& s, string& p, int i, int j) {
        if (i == s.size() && j == p.size()) return 2;
        if (i == s.size() && p[j] != '*') return 0;
        if (j == p.size()) return 1;
        if (s[i] == p[j] || p[j] == '?') {
            return helper(s, p, i + 1, j + 1);
        }
        if (p[j] == '*') {
            if (j + 1 < p.size() && p[j + 1] == '*') {
                return helper(s, p, i, j + 1);
            }
            for (int k = 0; k <= (int)s.size() - i; ++k) {
                int res = helper(s, p, i + k, j + 1);
                if (res == 0 || res == 2) return res;
            }
        }
        return 1;
    }
};文章来源地址https://www.toymoban.com/news/detail-631724.html

到了这里,关于动态规划--通配字符串匹配的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:  s.length≤40000 s.length≤40000 示例: 输入: 返回值: 说明

    2024年02月06日
    浏览(58)
  • 【算法】力扣【动态规划,LCS】1312. 让字符串成为回文串的最少插入次数

    1312. 让字符串成为回文串的最少插入次数 本文探讨的是力扣(LeetCode)上的第1312题:让字符串成为回文串的最少插入次数。这是一道属于动态规划类别下的困难题目,通常以回文串相关的操作来衡量算法的优化和执行效率。 问题的核心是给定一个字符串 s ,你可以在任意位

    2024年01月23日
    浏览(50)
  • 【算法|动态规划No.28】leetcode1312. 让字符串成为回文串的最少插入次数

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(57)
  • 【字符串匹配】暴力匹配算法

    ​ 暴力匹配算法,也称为朴素字符串匹配算法,是一种简单但不高效的字符串匹配方法。它的原理非常直观,其主要思想是逐个字符地比较文本串和模式串,从文本串的每个可能的起始位置开始,依次检查是否有匹配的子串。以下是暴力匹配算法的详细原理: 1. 一个字一个

    2024年02月09日
    浏览(53)
  • 【动态规划】【字符串】扰乱字符串

    视频算法专题 动态规划汇总 字符串 使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止 如果字符串的长度 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符

    2024年02月03日
    浏览(60)
  • 字符串查找匹配算法

    字符串匹配(查找)是字符串的一种基本操作:给定带匹配查询的文本串S和目标子串T,T也叫做模式串。在文本S中找到一个和模式T相符的子字符串,并返回该子字符串在文本中的位置。 Brute Force Algorithm,也叫朴素字符串匹配算法,Naive String Matching Algorithm。 基本思路就是将

    2024年02月14日
    浏览(58)
  • 【数据结构】数组和字符串(十四):字符串匹配1:朴素的模式匹配算法(StringMatching)

      字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列,简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作: S = ′ ′ a 0 a 1 … a n − 1 ′ ′ S=\\\'\\\'a_{0} a_{1}…a_{n-1}\\\'\\\' S = ′′ a 0 ​ a 1 ​ … a n − 1 ′′ ​   其中S是串名,引号中

    2024年02月05日
    浏览(73)
  • 【kmp算法】字符串匹配

    kmp算法解决的是字符串匹配的问题,具体来说假定我们要在主串s[ ] 中匹配模式串p[ ],找到匹配到的位置loc; 最自然的想法是暴力写法 (BF)枚举主串字符s[ i ] ,和模式串p[ j ]。一个一个匹配,如果匹配失败,i指针回退回起点,往前进一位,再次进行比较,知道匹配成功。

    2024年02月04日
    浏览(76)
  • 字符串匹配-KMP算法

    KMP算法,字符串匹配算法,给定一个主串S,和一个字串T,返回字串T与之S匹配的数组下标。 在学KMP算法之前,对于两个字符串,主串S,和字串T,我们根据暴力匹配,定义两个指针,i指向主串S的起始,j指向字串T的起始,依次比较,如果 主串i位置的值等于子串j位置的值,

    2024年02月14日
    浏览(55)
  • 字符串匹配算法:KMP

    Knuth–Morris–Pratt(KMP)是由三位数学家克努斯、莫里斯、普拉特同时发现,所有人们用三个人的名字来称呼这种算法,KMP是一种改进的字符串匹配算法,它的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n) 字

    2024年02月06日
    浏览(62)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包