一、通配符匹配
题目描述:
给你一个输入字符串 (s) 和一个字符模式 § ,请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配:
- ‘?’ 可以匹配任何单个字符。
- ‘*’ 可以匹配任意字符序列(包括空字符序列)。
判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
输入:s = “aa”, p = “a”
输出:false
解释:“a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:s = “aa”, p = ""
输出:true
解释:'’ 可以匹配任意字符串。
示例 3:
输入:s = “cb”, p = “?a”
输出:false
解释:‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
1.1 思路分析
我们可以分别以i和j表示s[0~i]
和p[0~j]
是否能成功匹配。
那么这里就只用讨论i
和j
的位置,有四种情况:
1️⃣ 如果s[i] == p[j]
,那么我们就只用判断dp[i - 1][j - 1]
是否能成功匹配,如果能成功匹配,那么说明加上i
和j
的位置也能成功匹配。
状态转移方程:dp[i][j] = s[i] == p[j] && dp[i - 1][j - 1]
2️⃣ 如果p[j] == '?'
那么说明此时s[i]不管是什么都可以,只需要判断dp[i - 1][j - 1]
是否能成功匹配,就跟上面一样。
状态转移方程:dp[i][j] = p[j] == '?' && dp[i - 1][j - 1]
3️⃣ 如果p[j] == '*'
,这里的情况就比较多,因为它可以变成0个或多个字符:
这么多情况只要有一种情况满足条件即可。
状态转移方程:
for(int k = 0; k <= i; k++)
{
if(dp[i - k][j - 1])
{
dp[i][j] = true;
break;
}
}
4️⃣ 如果p[j] != '?' && p[j] != '*' && p[j] != s[i]
,那么说明不能匹配。
1.2 初始化处理
我们看到状态转移方程会用到i-1
和j- 1
,所以dp表可以多开一维,而为了不改变下标的映射关系,我们可以在s串和p串的开头各自添加一个字符。
接下来就是初始化,首先dp[0][0]
就代表两个空串,一定能匹配。所以dp[0][0] = true
;
其次还有*
在p串开头的位置出现,因为*
可以变成空串,所以只要是开头的*
都可以跟s[0]匹配成功:dp[0][j] = true
;
1.3 代码
class Solution {
public:
bool isMatch(string s, string p) {
s = " " + s;
p = " " + p;
int n = s.size(), m = p.size();
vector<vector<bool>> dp(n, vector<bool>(m));
dp[0][0] = true;
for(int j = 1; j < m; j++)
{
if(p[j] == '*')
{
dp[0][j] = true;
}
else break;
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if((p[j] == '?' && dp[i - 1][j - 1]))
{
dp[i][j] = true;
}
else if(s[i] == p[j] && dp[i - 1][j - 1])
{
dp[i][j] = true;
}
else if(p[j] == '*')
{
for(int k = 0; k <= i; k++)
{
if(dp[i - k][j - 1])
{
dp[i][j] = true;
break;
}
}
}
}
}
return dp[n - 1][m - 1];
}
};
1.4 优化
p[j] == '*'
这种情况其实可以写成:
而经过观察可以再写出一个式子:
经过观察可以发现蓝色框框圈起来的部分是相等的
所以可以写成:
class Solution {
public:
bool isMatch(string s, string p) {
s = " " + s;
p = " " + p;
int n = s.size(), m = p.size();
vector<vector<bool>> dp(n, vector<bool>(m));
dp[0][0] = true;
for(int j = 1; j < m; j++)
{
if(p[j] == '*') dp[0][j] = true;
else break;
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(dp[i - 1][j - 1] && (p[j] == '?' || s[i] == p[j])) dp[i][j] = true;
else if(p[j] == '*')
{
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[n - 1][m - 1];
}
};
二、正则表达式匹配
题目描述:
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘.’ 匹配任意单个字符
- ‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
示例 1:
输入:s = “aa”, p = “a”
输出:false
解释:“a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:s = “aa”, p = “a*”
输出:true
解释:因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:s = “ab”, p = “."
输出:true
解释:".” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。
这里的.
字符跟上面一道题的?
作用是一样的。但是*
字符又区别,它的作用是把*
字符的前一个字符重复0次或者多次,比方说"a*"
它可以变成:""
,"a"
,"aa"
,"aaa"
……
2.1 思路分析
这里的有些情况跟上面的重复:
当dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j])
的时候,dp[i][j]=true
。
接下来只剩p[j] == '*'
的情况:
这里要分情况讨论j
的前一个元素,如果前一个元素是.
,那么也就是可以变成任意的多个字符,既然要匹配多个字符,那么又是跟上面一个题一样要讨论到底变成多长。因为上面讲过优化版,所以这里直接写:
接下来如果前面一个字符是普通字符:
这里解释以下:空自然不用说,当只变成长度为1的字符串时,首先要判断j
的前一个字符是否等于s[i]
,如果不相等就不用考虑前面的了。文章来源:https://www.toymoban.com/news/detail-470521.html
2.2 初始化设置
还是跟上面一样多加一维,然后让dp[0][0] = true
,接下来就是看p的前面全部是x*x*
……这种字符串的情况:文章来源地址https://www.toymoban.com/news/detail-470521.html
for(int j = 2; j < m; j += 2)
{
if(p[j] == '*') dp[0][j] = true;
else break;
}
2.3 代码
class Solution {
public:
bool isMatch(string s, string p) {
s = " " + s;
p = " " + p;
int n = s.size(), m = p.size();
vector<vector<bool>> dp(n, vector<bool>(m + 1));
dp[0][0] = true;
for(int j = 2; j < m; j += 2)
{
if(p[j] == '*') dp[0][j] = true;
else break;
}
for(int i = 1; i < n; i++)
{
for(int j = 1; j < m; j++)
{
if(p[j] == '*')
{
if(p[j - 1] == '.')
{
dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
}
else
{
dp[i][j] = dp[i][j - 2] || (s[i] == p[j - 1] && dp[i - 1][j]);
}
}
else
{
dp[i][j] = dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j]);
}
}
}
return dp[n - 1][m - 1];
}
};
到了这里,关于【动态规划】通配符匹配与正则表达式匹配的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!