LeetCode 通配符匹配
给定一个字符串 (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 = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输入: false
思路分析：对于这种字符串匹配的题，比较常用的思路就是利用递归进行求解，因为*号可以当做匹配空字符串，一个、多个字符等情况，非递归算法比较难以处理此问题。
递归思路，但含bug
class Solution {
public:
bool isMatch(string &s, int sIndex, string &p, int pIndex){
if (sIndex == s.size() && pIndex == p.size()){//只用当完全匹配才算成功
return true;
}
else if (sIndex < s.size() && pIndex < p.size()){
if (p[pIndex] == '*'){//遇到*号符
//*匹配空字符串 或者 跳过s[sIndex] 或者把 *号当做？
return isMatch(s, sIndex + 1, p, pIndex) || isMatch(s, sIndex, p, pIndex + 1) || isMatch(s, sIndex + 1, p, pIndex + 1);
}
else if (p[pIndex] == '?' || s[sIndex] == p[pIndex]){//遇到?号符或者字符相同
return isMatch(s, sIndex + 1, p, pIndex + 1);
}
else{
return false;
}
}
else {
return false;
}
}
bool isMatch(string s, string p) {
return isMatch(s, 0, p, 0);
}
};
原因是对于多出的号符未进行处理…
增加对多余号的处理算法：
class Solution {
public:
bool isMatch(string &s, int sIndex, string &p, int pIndex){
if (sIndex == s.size() && pIndex == p.size()){//只用当完全匹配才算成功
return true;
}
else if (sIndex < s.size() && pIndex < p.size()){
if (p[pIndex] == '*'){//遇到*号符
//*匹配空字符串 或者 跳过s[sIndex] 或者把 *号当做？
return isMatch(s, sIndex + 1, p, pIndex) || isMatch(s, sIndex + 1, p, pIndex + 1) || isMatch(s, sIndex, p, pIndex + 1);
}
else if (p[pIndex] == '?' || s[sIndex] == p[pIndex]){//遇到?号符或者字符相同
return isMatch(s, sIndex + 1, p, pIndex + 1);
}
else{
return false;
}
}
else if (pIndex < p.size()){//对末端多余的*号符进行处理
while (pIndex < p.size() && p[pIndex] == '*'){
++pIndex;
}
if (pIndex == p.size()){
return true;
}
}
return false;
}
bool isMatch(string s, string p) {
return isMatch(s, 0, p, 0);
}
};
递归算法实在耗时间。。。
修改为非递归算法代码
利用标记法，当遇到*号时，标记s串已匹配到的位置、*号出现的位置。方便再次滚回去进行处理
class Solution {
public:
bool isMatch(string s, string p) {
int sIndex = 0, pIndex = 0;
int sLength = s.size();
int pLength = p.size();
int match = 0;//记录遇到*号时，已经匹配到的下标位置
int star = -1;//标记*号的位置
//扫描s串
while (sIndex < sLength) {
if (pIndex < pLength && (s[sIndex] == p[pIndex] || p[pIndex] == '?')) {
++sIndex;//遇到字符相同，或者？号
++pIndex;
}
else if (pIndex < pLength && p[pIndex] == '*') {
star = pIndex;//遇到*号，标记*号的位置
match = sIndex;//记录已经匹配到s串的下标位置
++pIndex;//首先当做匹配空字符串
}
else if (star != -1) {//如果标记到了*号，执行到此说一次没有匹配成功，此处将再次对*号处理的方法进行更换
pIndex = star + 1;
++match;//此处match每次自增一次，表示*号匹配的字符增加了一个，并进行下一次的尝试
sIndex = match;//更新sIndex为*号匹配n个字符
}
else {
return false;
}
}
//处理多余的*号
while (pIndex < p.length() && p[pIndex] == '*') {
++pIndex;
}
return pIndex == pLength;
}
};
动态规划算法实现
class Solution {
public:
bool isMatch(string s, string p) {
int sLength = s.size(), pLength = p.size();
vector<vector<bool>> dp(sLength + 1, vector<bool>(pLength + 1, false));
dp[0][0] = true;//dp[i][j]代表s串下标从0到i和p串下标从0到j是否匹配
for (int i = 1; i <= pLength; ++i) {
if (p[i - 1] == '*') //*号匹配空字符串，初始化
dp[0][i] = dp[0][i - 1];
}
for (int i = 1; i <= sLength; ++i) {
for (int j = 1; j <= pLength; ++j) {
if (p[j - 1] == '*') {
//dp[i][j] = dp[i - 1][j]表示替代了一个字符，且还保留*号
//dp[i][j] = dp[i - 1][j - 1]表示*号只匹配一个字符
//dp[i][j] = dp[i][j - 1]表示跳过了*号符
dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
}
else {
//如果字符相等或者？号
dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
}
}
}
return dp[sLength][pLength];
}
};
动态规划算法的方程转移是关键，请仔细斟酌一下里面的转移方程。