題意：s是空串或包含a-z字母；

p為包含a-z字母或？或 * （其中*可以匹配任意字符串包括空串，？可以匹配任意字符）。

思路：

1）特殊情況：當s為空串時，p為連續 * 時，則連續 * 的位置都為true。

2）若p的第j個字符為 * ，分兩種情況：

a)? 若p中的前 j-1個字符和 s 中的前 i 個字符匹配成功了， 即 dp[i][j-1] == true , 因為 * 可以匹配空串，則 dp[i][j] == true;

b)? 若p中的前 j 個字符和 s 中前 i-1 個字符匹配成功了，即 dp[i-1][j] == true , 因為 * 可以匹配任意字符串，則 dp[i][j] == true.

3) ? 若p中的第j個字符不是 * 時，則需要滿足 dp[i-1][j-1] == true 和 s 中的第i個字符和p中的第j個字符相等， 即 s[i-1] == p[j-1], 或者 p中的第j個字符是問號, 即 p[j-1] == '?' 則 dp[i][j] == true.

注意：dp[][] 初始化申請空間大小要為 (m+1, n+1) ，因為dp[0][0] 為p和s為空串時候的情況。

dp如果用二維數組定義會超時！所以用二維vector。

注：s[i-1] 代表s中第i位字符。

class Solution { public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();//dp[i][j]:s中前i個字符組成的子串和p中前j個字符組成的子串是否能匹配//bool dp[m+1][n+1] = {false};vector<vector<bool> > dp(m+1, vector<bool>(n+1, false));//s,p都為空，返回0dp[0][0] = true;//s為空， p為連續星號時,賦值為truefor(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];elsedp[i][j] = (s[i-1]==p[j-1] || p[j-1] == '?') && dp[i-1][j-1];}}return dp[m][n];} };

?

?

轉載于:https://www.cnblogs.com/Bella2017/p/10644299.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的leetcode 44 字符匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。