10. 正則表達(dá)式匹配（困難）

1. 題解

   • 如果從左向右進(jìn)行匹配的話，需要考慮字符后是否有 * 。

     

   • 因此選擇從右向左掃描更為簡(jiǎn)單。

     *前面肯定有一個(gè)字符，它像是一個(gè)拷貝器，能夠復(fù)制前面的單個(gè)字符，甚至也可以把這個(gè)字符消除（出現(xiàn) 0 次）。

     兩個(gè)字符串是否匹配，取決于最右邊的字符是否匹配，以及剩余的子串是否匹配。其中，「剩余的子串是否匹配」，就是本道題的子問(wèn)題。

     

   • 狀態(tài)定義：定義 dp[i][j] 為第一個(gè)字符串到 i 為止，第二個(gè)字符串到 j 為止，兩個(gè)字符串是否匹配。如果匹配，dp[i][j] = true；如果不匹配，dp[i][j] = false。

   • 子問(wèn)題的考慮

     • 情況一：s[i-1] 和 p[j-1] 匹配，即 s[i-1] == p[j-1] || p[j-1] == '.'。那么只需要考慮剩余的子串是否匹配，即 dp[i][j] = dp[i-1][j-1];

       

     • 情況二：s[i-1] 和 p[j-1] 不匹配。這時(shí)候不能直接認(rèn)為兩個(gè)字符串不匹配，而是需要進(jìn)一步考慮 p[j-1] == '*' 的情況。但是如果不是 * ，那么肯定不匹配。

       

       對(duì)于 * ，它可以匹配 0 個(gè)或多個(gè)字符。當(dāng)s[i-1] 和 p[j-2] 匹配，且 p[j-1] == ‘*’ 時(shí)，需要考慮三種情況： * 使 dp[j-2] 出現(xiàn) 0 次、1 次或 >=2次。只要其中一種情況能使得兩個(gè)子串匹配，我們就可以繼續(xù)考慮剩余子串是否匹配。狀態(tài)轉(zhuǎn)移方程為：dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];

       
       當(dāng)s[i-1] 和 p[j-2] 不匹配，且 p[j-1] == ‘*’ 時(shí)，可以利用 * 消除不匹配字符 p[j-2]，考慮 s[i-1] 和 p[j-3] 是否匹配。狀態(tài)轉(zhuǎn)移方程為：dp[i][j] = dp[i][j-2];。

   • 初始情況：當(dāng)兩個(gè)字符串都是空串的時(shí)候，一定匹配，因此 dp[0][0] = true; ；當(dāng) s 為空時(shí)，如果 p 的右端字符是 * ，那么就可以使得 p 也變成空串；當(dāng) p 為空，兩個(gè)字符串一定不匹配。

2. 代碼

   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));// 兩個(gè)空字符串一定匹配dp[0][0] = true;// 如果s為空串 p[j-1]=* 也能夠匹配for(int j=1; j<=n; ++j){if(p[j-1] == '*'){dp[0][j] = dp[0][j-2];}}// 從右向左匹配for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){// s[i-1]和p[j-1]匹配if(s[i-1] == p[j-1] || p[j-1] == '.'){dp[i][j] = dp[i-1][j-1];}// s[i-1]和p[j-1]不匹配else{// p[j-1] == '*' 且 s[i-1]和p[j-2]匹配if(p[j-1] == '*'){dp[i][j] = dp[i][j-2];if(s[i-1] == p[j-2] || p[j-2] == '.'){dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];}}}}}return dp[m][n];}
   };
   

3. 收獲

   • 理解錯(cuò)了 * 的意思，* 類似于一個(gè)拷貝器 ，能匹配前一個(gè)元素，也能消除前一個(gè)元素（匹配零個(gè)）。
   • 這道題需要考慮多種情況，感覺(jué)很難想得這么全面。