LeetCode 10. 正則運算式匹配

動態規劃解題要考慮狀態表示和狀態計算
狀態表示分為集合含義和輸出屬性
本題用 f ( i , j ) f(i,j) f(i,j)狀態表示， s s s是原字串， p p p是字符規律字串
集合：所有 s [ 1 ～ i ] s[1 \sim i] s[1～i]和 p [ 1 ～ j ] p[1 \sim j] p[1～j]的匹配方案
屬性：bool值，是否存在一個合法方案
狀態計算
1.如果 p [ j ] ≠ ′ ? ′ p[j] \neq '*' p[j]?=′?′，那么 f ( i , j ) = ( s [ i ] = = p [ j ] ∣ ∣ p [ j ] = = ′ . ′ ) & & f [ i ? 1 , j ? 1 ] f(i, j) = (s[i] == p[j] || p[j] == '.') \& \& f[i-1, j-1] f(i,j)=(s[i]==p[j]∣∣p[j]==′.′)&&f[i?1,j?1]
2.如果 p [ j ] = = ′ ? ′ p[j] == '*' p[j]==′?′,那么需要列舉匹配0個字符，1個字符， 匹配2個字符…
f ( i , j ? 2 ) ∣ f ( i ? 1 , j ? 2 ) & s [ i ] = = p [ j ] ∣ f ( i ? 2 , j ? 2 ) & s [ i ] = = p [ j ] & s [ i ? 1 ] = = p [ j ? 1 ] ∣ . . . f(i, j - 2) | f(i - 1, j - 2) \& s[i] == p[j] | f(i-2, j-2) \& s[i] == p[j] \& s[i - 1] == p[j - 1]|... f(i,j?2)∣f(i?1,j?2)&s[i]==p[j]∣f(i?2,j?2)&s[i]==p[j]&s[i?1]==p[j?1]∣...
狀態數量是 O ( n 2 ) O(n^2) O(n2)，轉移全部列舉一遍所以是 O ( n ) O(n) O(n)，整個時間復雜度是 O ( n 3 ) O(n^3) O(n3)
這個式子沒辦法被計算機求解，后來發現

所以，總結規律 f ( i , j ) = f ( i , j ? 2 ) ∣ f ( i ? 1 , j ) & s i = = p j f(i, j) = f(i, j - 2) | f(i - 1, j) \& s_i == p_j f(i,j)=f(i,j?2)∣f(i?1,j)&si?==pj?

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;

        for(int i = 0; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(j + 1 <= m && p[j + 1] == '*') continue;
                if(i && p[j] != '*'){
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }else if(p[j] == '*'){
                    if(j == 1) continue;
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            } 
        }
        return f[n][m];
    }
};