1. 題目來(lái)源
鏈接：通配符匹配
來(lái)源：LeetCode

2. 題目說(shuō)明
給定一個(gè)字符串 (s) 和一個(gè)字符模式 § ，實(shí)現(xiàn)一個(gè)支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何單個(gè)字符。
‘*’ 可以匹配任意字符串（包括空字符串）。

兩個(gè)字符串完全匹配才算匹配成功。

說(shuō)明:

s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。
示例1：

輸入:
s = “aa”
p = “a”
輸出: false
解釋: “a” 無(wú)法匹配 “aa” 整個(gè)字符串。

示例2：

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

示例3：

輸入:
s = “cb”
p = “?a”
輸出: false
解釋: ‘?’ 可以匹配 ‘c’, 但第二個(gè) ‘a(chǎn)’ 無(wú)法匹配 ‘b’。

示例4：

輸入:
s = “adceb”
p = “ab”
輸出: true
解釋: 第一個(gè) ‘’ 可以匹配空字符串, 第二個(gè) '’ 可以匹配字符串 “dce”.

示例5：

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

題目解析

方法一：

樸素遍歷解法、考慮條件繁多
這道題通配符匹配問(wèn)題還是小有難度的，有特殊字符 ‘ * ’ 和 ‘?’，其中 ‘?’ 能代替任何字符，‘*’ 能代替任何字符串。這道題最大的難點(diǎn)，就是對(duì)于星號(hào)的處理，可以匹配任意字符串，簡(jiǎn)直像開了掛一樣，有以下幾點(diǎn)：

在星號(hào)對(duì)應(yīng)位置之前，不管你s中有任何字符串，我大星號(hào)都能匹配你，主角光環(huán)啊。
但即便叼如斯的星號(hào)，也有其處理不了的問(wèn)題，那就是一旦p中有s中不存在的字符，那么一定無(wú)法匹配，因?yàn)樾翘?hào)只能增加字符，不能消除字符。
再有就是星號(hào)一旦確定了要匹配的字符串，對(duì)于星號(hào)位置后面的匹配情況也就鞭長(zhǎng)莫及了。
所以p串中星號(hào)的位置很重要，用 jStar 來(lái)表示，還有星號(hào)匹配到s串中的位置，使用 iStart 來(lái)表示，這里 iStar 和 jStar 均初始化為 -1，表示默認(rèn)情況下是沒(méi)有星號(hào)的。然后再用兩個(gè)變量i和j分別指向當(dāng)前s串和p串中遍歷到的位置。

開始進(jìn)行匹配：

若i小于s串的長(zhǎng)度，進(jìn)行 while 循環(huán)。
若當(dāng)前兩個(gè)字符相等，或著p中的字符是問(wèn)號(hào)，則i和j分別加1。
若 p[j] 是星號(hào)，要記錄星號(hào)的位置，jStar 賦為j，此時(shí)j再自增1，iStar 賦為i。
若當(dāng)前 p[j] 不是星號(hào)，并且不能跟 p[i] 匹配上，此時(shí)就要靠星號(hào)了，若之前星號(hào)沒(méi)出現(xiàn)過(guò)，那么就直接跪，比如 s = “aa” 和 p = “c*”，此時(shí) s[0] 和 p[0] 無(wú)法匹配，雖然 p[1] 是星號(hào)，但還是跪。如果星號(hào)之前出現(xiàn)過(guò)，可以強(qiáng)行續(xù)一波命，比如 s = “aa” 和 p = “*c”，當(dāng)發(fā)現(xiàn) s[1] 和 p[1] 無(wú)法匹配時(shí)，但是好在之前 p[0] 出現(xiàn)了星號(hào)，把 s[1] 交給 p[0] 的星號(hào)去匹配。至于如何知道之前有沒(méi)有星號(hào)，這時(shí)就能看出 iStar 的作用了，因?yàn)槠涑跏蓟癁?-1，而遇到星號(hào)時(shí)，其就會(huì)被更新為i，只要檢測(cè) iStar 的值，就能知道是否可以使用星號(hào)續(xù)命。
雖然成功續(xù)了命，匹配完了s中的所有字符，但是之后還要檢查p串，此時(shí)沒(méi)匹配完的p串里只能剩星號(hào)，不能有其他的字符，將連續(xù)的星號(hào)過(guò)濾掉，如果j不等于p的長(zhǎng)度，則返回 false，參見(jiàn)代碼如下：
// 執(zhí)行用時(shí) :8 ms, 在所有 C++ 提交中擊敗了94.73%的用戶
// 內(nèi)存消耗 :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;
? ? }
};

方法二：動(dòng)態(tài)規(guī)劃解法

這道題也能用動(dòng)態(tài)規(guī)劃來(lái)解，外卡匹配中的星號(hào)跟前面的字符沒(méi)有半毛錢關(guān)系，如果前面的字符沒(méi)有匹配上，那么直接返回 false 了，根本不用管星號(hào)。而星號(hào)存在的作用是可以表示任意的字符串，當(dāng)然只是當(dāng)匹配字符串缺少一些字符的時(shí)候起作用，當(dāng)匹配字符串p包含目標(biāo)字符串s中沒(méi)有的字符時(shí)，將無(wú)法成功匹配。

對(duì)于這種玩字符串的題目，動(dòng)態(tài)規(guī)劃是一大神器，因?yàn)樽址渥哟g的關(guān)系十分密切，正好適合 DP 這種靠推導(dǎo)狀態(tài)轉(zhuǎn)移方程的特性。

那么先來(lái)定義dp數(shù)組吧，使用一個(gè)二維 dp 數(shù)組，其中 dp[i][j] 表示 s中前 i 個(gè)字符組成的子串和 p 中前 j 個(gè)字符組成的子串是否能匹配。大小初始化為 (m+1) x (n+1)，加1的原因是要包含 dp[0][0] 的情況，因?yàn)槿魋和p都為空的話，也應(yīng)該返回 true，所以也要初始化 dp[0][0] 為 true。還需要提前處理的一種情況是，當(dāng)s為空，p為連續(xù)的星號(hào)時(shí)的情況。由于星號(hào)是可以代表空串的，所以只要s為空，那么連續(xù)的星號(hào)的位置都應(yīng)該為 true，所以先將連續(xù)星號(hào)的位置都賦為 true。

然后就是推導(dǎo)一般的狀態(tài)轉(zhuǎn)移方程，如何更新 dp[i][j]，首先處理比較 tricky 的情況：

若p中第j個(gè)字符是星號(hào)，由于星號(hào)可以匹配空串，所以如果p中的前 j-1 個(gè)字符跟s中前i個(gè)字符匹配成功了（ dp[i][j-1] 為true）的話，則 dp[i][j] 也能為 true?；蛘呷魀中的前j個(gè)字符跟s中的前i-1個(gè)字符匹配成功了（ dp[i-1][j] 為true ）的話，則 dp[i][j] 也能為 true（因?yàn)樾翘?hào)可以匹配任意字符串，再多加一個(gè)任意字符也沒(méi)問(wèn)題）。
若p中的第j個(gè)字符不是星號(hào)，對(duì)于一般情況，假設(shè)已經(jīng)知道了s中前 i-1 個(gè)字符和p中前 j-1 個(gè)字符的匹配情況（即 dp[i-1][j-1] ），現(xiàn)在只需要匹配s中的第i個(gè)字符跟p中的第j個(gè)字符，若二者相等（ s[i-1] == p[j-1] ），或者p中的第j個(gè)字符是問(wèn)號(hào)（ p[j-1] == ‘?’ ），再與上 dp[i-1][j-1] 的值，就可以更新 dp[i][j] 了，參見(jiàn)代碼如下：
// 執(zhí)行用時(shí) :116 ms, 在所有 C++ 提交中擊敗了43.78%的用戶
// 內(nèi)存消耗 :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];
? ? }
};

方法三：遞歸解法、剪枝

其實(shí)這道題也可以使用遞歸來(lái)做，因?yàn)樽哟蛘咦訑?shù)組這種形式，天然適合利用遞歸來(lái)做。但是愣了吧唧的遞歸跟暴力搜索并沒(méi)有啥太大的區(qū)別，很容易被 OJ 斃掉 ，參見(jiàn)代碼一：，有以下逐步優(yōu)化的思路：

首先判斷s串，若為空，那么再看p串，若p為空，則為 true，或者跳過(guò)星號(hào)，繼續(xù)調(diào)用遞歸。若s串不為空，且p串為空，則直接 false。若s串和p串均不為空，進(jìn)行第一個(gè)字符的匹配，若相等，或者 p[0] 是問(wèn)號(hào)，則跳過(guò)首字符，對(duì)后面的子串調(diào)用遞歸。若 p[0] 是星號(hào)，先嘗試跳過(guò)s串的首字符，調(diào)用遞歸，若遞歸返回 true，則當(dāng)前返回 true。否則嘗試跳過(guò)p串的首字符，調(diào)用遞歸，若遞歸返回 true，則當(dāng)前返回 true。但是很不幸，內(nèi)存超出限制了 MLE。做了簡(jiǎn)單的優(yōu)化，跳過(guò)了連續(xù)的星號(hào)，但是這次時(shí)間超出了限制 TLE，參見(jiàn)代碼二。思考想是不是取子串 substr() 操作太費(fèi)時(shí)間，且調(diào)用遞歸的適合s串和p串又分別建立了副本，才導(dǎo)致的 TLE。于是想著用坐標(biāo)變量來(lái)代替取子串，并且遞歸函數(shù)調(diào)用的s串和p串都加上引用，但尼瑪還是跪了。參見(jiàn)代碼三
找到一種神奇的剪枝的方法，這種解法的遞歸函數(shù)返回類型不是 bool 型，而是整型，有三種不同的狀態(tài)，返回0表示匹配到了s串的末尾，但是未匹配成功；返回1表示未匹配到s串的末尾就失敗了；返回2表示成功匹配。那么只有返回值大于1，才表示成功匹配。至于為何失敗的情況要分類，就是為了進(jìn)行剪枝。在遞歸函數(shù)中，若s串和p串都匹配完成了，返回狀態(tài)2。若s串匹配完成了，但p串但當(dāng)前字符不是星號(hào)，返回狀態(tài)0。若s串未匹配完，p串匹配完了，返回狀態(tài)1。若s串和p串均為匹配完，且當(dāng)前字符成功匹配的話，對(duì)下一個(gè)位置調(diào)用遞歸。否則若p串當(dāng)前字符是星號(hào)，首先跳過(guò)連續(xù)的星號(hào)。然后分別讓星號(hào)匹配空串，一個(gè)字符，兩個(gè)字符，…，直到匹配完整個(gè)s串，對(duì)每種情況分別調(diào)用遞歸函數(shù)，接下來(lái)就是最大的亮點(diǎn)了，也是最有用的剪枝，當(dāng)前返回值為狀態(tài)0或者2的時(shí)候，返回，否則繼續(xù)遍歷。如果僅僅是狀態(tài)2的時(shí)候才返回，會(huì)有大量的重復(fù)計(jì)算，因?yàn)楫?dāng)返回值為狀態(tài)0的時(shí)候，已經(jīng)沒(méi)有繼續(xù)循環(huán)下去的必要了，非常重要的一刀剪枝，參見(jiàn)代碼四如下：
代碼一：

// 超出時(shí)間限制
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;
? ? }
};
代碼二：

// 超出時(shí)間限制
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;
? ? }
};
代碼三：

// 超出時(shí)間限制
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;
? ? }
};
代碼四：

// 執(zhí)行用時(shí) :12 ms, 在所有 C++ 提交中擊敗了86.70%的用戶
// 內(nèi)存消耗 :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;
? ? }
};文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-631724.html

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃--通配字符串匹配的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！