10.jpeg

    代码 :

    1. class Solution {
    2. public:
    3.     bool isMatch(string s, string p) {
    4.         int n = s.size(), m = p.size(); 
    5.         s = ' ' + s, p = ' ' + p;
    7.         // s(0, i)  &&   p(0, j)  
    8.         vector<vector<bool>> dp(n+1, vector<bool>(m+1));
    10.         dp[0][0] = true;
    12.         for(int i = 0; i <= n; i ++) {
    13.             for(int j = 1; j <= m; j ++) {
    14.                 if(j + 1 <= m && p[j+1] == '*') continue; // *前缀 需要和* 一起使用 
    16.                 if(p[j] != '*') 
    17.                     dp[i][j] = (s[i] == p[j] || p[j] == '.') && i && dp[i-1][j-1];
    19.                 // v  -- va* dp[i][j-2] 
    20.                 // va -- va* dp[i-1][j-2]
    21.                 else if(p[j] == '*')
    22.                     dp[i][j] = dp[i][j-2] || i && (dp[i-1][j] && (s[i] == p[j-1] || p[j-1] == '.'));
    23.             }
    24.         }
    26.         return dp[n][m];
    27.     }
    28. };