動機

dp就是把所有可能性，encode成index在matrix上記錄，在求解時利用index去取得答案

Problem

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.​​​​
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

 

Example 1:

Input: s = aa, p = aOutput: falseExplanation: a does not match the entire string aa.

Example 2:

Input: s = aa, p = a*Output: trueExplanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes aa.

Example 3:

Input: s = ab, p = .*Output: trueExplanation: .* means zero or more (*) of any character (.).

Example 4:

Input: s = aab, p = c*a*bOutput: trueExplanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches aab.

Example 5:

Input: s = mississippi, p = mis*is*p*.Output: false

 

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Sol

// 0 is 沒初始化，1是match，-1是mismatch
int dp[1000][1000];
class Solution {
public:
    void initDP() {
        memset(dp, 0, sizeof(dp));
    }
    bool equalChar(char a,char b) {
        return b == '.' || a == b;
    }
    bool restAsterisk(int j,string& p) {
        for(;j >=0 && p[j]=='*';j-=2);
        return j < 0;
    }
    // i : S目前比對到哪
    // j : P目前比對到哪
    int f(int i,int j,string &S,string &P) {
        if(j < 0 && i < 0) // 都沒得比了就是match 
            return 1;
        else if(j < 0) // pattern沒得比，S還有剩，mismatch
            return -1;
        else if(i < 0) // pattern還有剩，S沒得比，看剩下的是不是都是星號
            return restAsterisk(j,P) ? 1 : -1;
        else if(dp[i][j] == 0) // 在dp上沒有被算過
            if(P[j] == '*') { // P是星號
                // 星號就要列舉沒match到所有能match的case
                dp[i][j] = f(i,j-2,S,P); // <c>* doesnt match anything
                for(int k=i;k>=0 && equalChar(S[k],P[j-1]);k--)
                    if(f(k-1,j-2,S,P)>0)
                        dp[i][j] = f(k-1,j-2,S,P);
                
            } else // P是字元
                dp[i][j] = equalChar(S[i],P[j]) ? f(i-1,j-1,S,P) : false;
        else;
        return dp[i][j];
    }
    bool isMatch(string s, string p) {
        initDP();
        return f(s.size()-1,p.size()-1,s,p) > 0;
    }
};

TODO

很明顯其他solution的code比較短要再review