題目如下：
給你一個字串 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
解釋：".*" 表示可匹配零個或多個（'*'）任意字符（'.'），
示例 4：
輸入：s = "aab" p = "c*a*b"
輸出：true
解釋：因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復一次，因此可以匹配字串 "aab"，
示例 5：
輸入：s = "mississippi" p = "mis*is*p*."
輸出：false
提示：
0 <= s.length <= 20
0 <= p.length <= 30
s 可能為空，且只包含從 a-z 的小寫字母，
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *，
保證每次出現字符 * 時，前面都匹配到有效的字符
初始思路：
剛開始的解題思路想的是挨個對比兩個字串，然后分三種不同的情況進行處理，分別是：
1）非特殊字符比較：
1.1）后為*號字符，且當前字符相等，這種情況太復雜了，要挨個列舉當前字符匹配的次數；
1.2）后不為*號字符，且當前字符相等，這種情況直接回傳false；
1.3）兩字符不相等，且后續為*號，則直接忽略當前字符和*號，進行剩余字符的比較，
2）當前字符為.：等同于非特殊符號相等的情況，
3）當前為*號，這個比較難處理，當時沒想出來，這道題也因此沒做出來，
答案思路：答案使用了動態規劃來解題，
和我的分類不同，不過有點共通的地方，按照*號來進行分類，
1）當前字符為*號，此時分為兩種情況；
1.1）此*號不起匹配作用，
1.2）當前*號進行一次匹配，同時*號繼續發揮作用，
2）當前字符不為*號，則按照非特殊字符的情況直接進行比較即可；
代碼如下：
/*進行字符的比較*/
bool matchChar(string & s, string & p,int i, int j) { if(i<0) { return false; }
/*匹配任意字符*/ if(p[j]=='.') { return true; } return s[i]==p[j]; } bool isMatch(string s, string p) { int m=s.size(),n=p.size();
/*注意這里需要分開理解，vecDp[i][j]表示的是S的前i個字符與P的前j個字符匹配；后面進行字符匹配時，要注意下標的選擇*/ vector<vector<int>> vecDp(m+1,vector<int>(n+1)); vecDp[0][0]=1; for(int i=0;i<=m;i++) { for(int j=1;j<=n;j++) {
/*對應的第一種情況*/ if(p[j-1]=='*') {
/*注意這里是|=運算子*/ vecDp[i][j]|=vecDp[i][j-2]; if(matchChar(s,p,i-1,j-2)) {
/*同上，注意這里是|=運算子*/ vecDp[i][j]|=vecDp[i-1][j]; } }
/*對應的第二種情況*/ else { if(matchChar(s,p,i-1,j-1)) { vecDp[i][j]=vecDp[i-1][j-1]; } } } } return vecDp[m][n]; }
復雜度：
時間和空間復雜度都未O(m*n)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259937.html
標籤：其他
上一篇：性能測驗整體認知