C++實現(xiàn)LeetCode(44.外卡匹配)
[LeetCode] 44. Wildcard Matching 外卡匹配
Given an input string (s
) and a pattern (p
), implement wildcard pattern matching with support for '?'
and '*'
.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s
could be empty and contains only lowercase lettersa-z
.p
could be empty and contains only lowercase lettersa-z
, and characters like?
or*
.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.
Example 3:
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
這道題通配符外卡匹配問題還是小有難度的,有特殊字符 ‘*’ 和 ‘?’,其中 ‘?’ 能代替任何字符,‘*’ 能代替任何字符串,注意跟另一道 Regular Expression Matching 正則匹配的題目區(qū)分開來。兩道題的星號的作用是不同的,注意對比區(qū)分一下。這道題最大的難點,就是對于星號的處理,可以匹配任意字符串,簡直像開了掛一樣,就是說在星號對應位置之前,不管你s中有任何字符串,我大星號都能匹配你,主角光環(huán)啊。但即便叼如斯的星號,也有其處理不了的問題,那就是一旦p中有s中不存在的字符,那么一定無法匹配,因為星號只能增加字符,不能消除字符,再有就是星號一旦確定了要匹配的字符串,對于星號位置后面的匹配情況也就鞭長莫及了。所以p串中星號的位置很重要,用 jStar 來表示,還有星號匹配到s串中的位置,使用 iStart 來表示,這里 iStar 和 jStar 均初始化為 -1,表示默認情況下是沒有星號的。然后再用兩個變量i和j分別指向當前s串和p串中遍歷到的位置。
開始進行匹配,若i小于s串的長度,進行 while 循環(huán)。若當前兩個字符相等,或著p中的字符是問號,則i和j分別加1。若 p[j] 是星號,要記錄星號的位置,jStar 賦為j,此時j再自增1,iStar 賦為i。若當前 p[j] 不是星號,并且不能跟 p[i] 匹配上,此時就要靠星號了,若之前星號沒出現(xiàn)過,那么就直接跪,比如 s = "aa" 和 p = "c*",此時 s[0] 和 p[0] 無法匹配,雖然 p[1] 是星號,但還是跪。如果星號之前出現(xiàn)過,可以強行續(xù)一波命,比如 s = "aa" 和 p = "*c",當發(fā)現(xiàn) s[1] 和 p[1] 無法匹配時,但是好在之前 p[0] 出現(xiàn)了星號,把 s[1] 交給 p[0] 的星號去匹配。至于如何知道之前有沒有星號,這時就能看出 iStar 的作用了,因為其初始化為 -1,而遇到星號時,其就會被更新為i,只要檢測 iStar 的值,就能知道是否可以使用星號續(xù)命。雖然成功續(xù)了命,匹配完了s中的所有字符,但是之后還要檢查p串,此時沒匹配完的p串里只能剩星號,不能有其他的字符,將連續(xù)的星號過濾掉,如果j不等于p的長度,則返回 false,參見代碼如下:
解法一:
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; } };
這道題也能用動態(tài)規(guī)劃 Dynamic Programming 來解,寫法跟之前那道題 Regular Expression Matching 很像,但是還是不一樣。外卡匹配和正則匹配最大的區(qū)別就是在星號的使用規(guī)則上,對于正則匹配來說,星號不能單獨存在,前面必須要有一個字符,而星號存在的意義就是表明前面這個字符的個數(shù)可以是任意個,包括0個,那么就是說即使前面這個字符并沒有在s中出現(xiàn)過也無所謂,只要后面的能匹配上就可以了。而外卡匹配就不是這樣的,外卡匹配中的星號跟前面的字符沒有半毛錢關(guān)系,如果前面的字符沒有匹配上,那么直接返回 false 了,根本不用管星號。而星號存在的作用是可以表示任意的字符串,當然只是當匹配字符串缺少一些字符的時候起作用,當匹配字符串p包含目標字符串s中沒有的字符時,將無法成功匹配。
對于這種玩字符串的題目,動態(tài)規(guī)劃 Dynamic Programming 是一大神器,因為字符串跟其子串之間的關(guān)系十分密切,正好適合 DP 這種靠推導狀態(tài)轉(zhuǎn)移方程的特性。那么先來定義dp數(shù)組吧,使用一個二維 dp 數(shù)組,其中 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為連續(xù)的星號時的情況。由于星號是可以代表空串的,所以只要s為空,那么連續(xù)的星號的位置都應該為 true,所以先將連續(xù)星號的位置都賦為 true。然后就是推導一般的狀態(tài)轉(zhuǎn)移方程了,如何更新 dp[i][j],首先處理比較 tricky 的情況,若p中第j個字符是星號,由于星號可以匹配空串,所以如果p中的前 j-1 個字符跟s中前i個字符匹配成功了( dp[i][j-1] 為true)的話,則 dp[i][j] 也能為 true?;蛘呷魀中的前j個字符跟s中的前i-1個字符匹配成功了( dp[i-1][j] 為true )的話,則 dp[i][j] 也能為 true(因為星號可以匹配任意字符串,再多加一個任意字符也沒問題)。若p中的第j個字符不是星號,對于一般情況,假設已經(jīng)知道了s中前 i-1 個字符和p中前 j-1 個字符的匹配情況(即 dp[i-1][j-1] ),現(xiàn)在只需要匹配s中的第i個字符跟p中的第j個字符,若二者相等( s[i-1] == p[j-1] ),或者p中的第j個字符是問號( p[j-1] == '?' ),再與上 dp[i-1][j-1] 的值,就可以更新 dp[i][j] 了,參見代碼如下:
解法二:
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ù)組這種形式,天然適合利用遞歸來做。但是愣了吧唧的遞歸跟暴力搜索并沒有啥太大的區(qū)別,很容易被 OJ 斃掉,比如評論區(qū)六樓的那個 naive 的遞歸,其實完全是按照題目要求來的。首先判斷s串,若為空,那么再看p串,若p為空,則為 true,或者跳過星號,繼續(xù)調(diào)用遞歸。若s串不為空,且p串為空,則直接 false。若s串和p串均不為空,進行第一個字符的匹配,若相等,或者 p[0] 是問號,則跳過首字符,對后面的子串調(diào)用遞歸。若 p[0] 是星號,先嘗試跳過s串的首字符,調(diào)用遞歸,若遞歸返回 true,則當前返回 true。否則嘗試跳過p串的首字符,調(diào)用遞歸,若遞歸返回 true,則當前返回 true。但是很不幸,內(nèi)存超出限制了 MLE,那么博主做了個簡單的優(yōu)化,跳過了連續(xù)的星號,參見評論區(qū)七樓的代碼,但是這次時間超出了限制 TLE。博主想是不是取子串 substr() 操作太費時間,且調(diào)用遞歸的適合s串和p串又分別建立了副本,才導致的 TLE。于是想著用坐標變量來代替取子串,并且遞歸函數(shù)調(diào)用的s串和p串都加上引用,代碼參見評論區(qū)八樓,但還是跪了,OJ 大佬,刀下留人啊。最后還是在論壇上找到了一個使用了神奇的剪枝的方法,這種解法的遞歸函數(shù)返回類型不是 bool 型,而是整型,有三種不同的狀態(tài),返回0表示匹配到了s串的末尾,但是未匹配成功;返回1表示未匹配到s串的末尾就失敗了;返回2表示成功匹配。那么只有返回值大于1,才表示成功匹配。至于為何失敗的情況要分類,就是為了進行剪枝。在遞歸函數(shù)中,若s串和p串都匹配完成了,返回狀態(tài)2。若s串匹配完成了,但p串但當前字符不是星號,返回狀態(tài)0。若s串未匹配完,p串匹配完了,返回狀態(tài)1。若s串和p串均為匹配完,且當前字符成功匹配的話,對下一個位置調(diào)用遞歸。否則若p串當前字符是星號,首先跳過連續(xù)的星號。然后分別讓星號匹配空串,一個字符,兩個字符,....,直到匹配完整個s串,對每種情況分別調(diào)用遞歸函數(shù),接下來就是最大的亮點了,也是最有用的剪枝,當前返回值為狀態(tài)0或者2的時候,返回,否則繼續(xù)遍歷。如果僅僅是狀態(tài)2的時候才返回,就像評論區(qū)八樓的代碼,會有大量的重復計算,因為當返回值為狀態(tài)0的時候,已經(jīng)沒有繼續(xù)循環(huán)下去的必要了,非常重要的一刀剪枝,參見代碼如下:
解法三:
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; } };
到此這篇關(guān)于C++實現(xiàn)LeetCode(44.外卡匹配)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)外卡匹配內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++實現(xiàn)LeetCode(55.跳躍游戲)
- C++實現(xiàn)LeetCode(45.跳躍游戲之二)
- C++實現(xiàn)LeetCode(769.可排序的最大塊數(shù))
- C++實現(xiàn)LeetCode(768.可排序的最大塊數(shù)之二)
- C++實現(xiàn)LeetCode(84.直方圖中最大的矩形)
- C++實現(xiàn)LeetCode(42.收集雨水)
- C++實現(xiàn)LeetCode(11.裝最多水的容器)
- C++實現(xiàn)LeetCode(10.正則表達式匹配)
- C++實現(xiàn)LeetCode(12.整數(shù)轉(zhuǎn)化成羅馬數(shù)字)
相關(guān)文章
在C++程序中開啟和禁用Windows設備的無線網(wǎng)卡的方法
這篇文章主要介紹了在C++程序中開啟和禁用Windows設備的無線網(wǎng)卡的方法,包括一些常見錯誤的分析與解決,需要的朋友可以參考下2016-03-03