19. regular expression matching

The finger of the sword Offer 19. Regular Expression Matching

Ideas ： Dynamic programming

State definition ：dp[i] [j] Representative string s Before i Characters and p Before j Whether characters match

Transfer equation ： We need to pay attention to , because dp[0] [0] Represents the status of empty characters , therefore dp[i] [j] The corresponding added character is s[i-1] and p[j-1]

• When p[j-1] = '*' when ,dp[i] [j] In any of the following cases: true When is true：
  • dp[i] [j-2]: About to combine characters p[j-2]p[j-1] regard as 0 Time
  • dp[i-1] [j] And s[i-1]==p[j-2]： Instant character p[j-2] Whether it matches when it occurs more than once
  • dp[i-1] [j] And p[j-2]==’.’: Instant character ’.' There are more 1 Whether the times match
• When dp[j-1]!=’*' when ,dp[i] [j] In any of the following cases: true When is true：
  • dp[i-1] [j-1] And s[i-1]==p[j-1]： Instant character s[i-1] and p[j-1] matching
  • dp[i-1] [j-1] And p[j-1]==’.’： I'm going to change the character ’.' Treat as character s[i-1] Whether time matches

initialization ： It needs to be initialized dp First line , To avoid index out of bounds during state transition .

• dp[0] [0]=true： representative 2 Whether the empty characters match
• dp[0] [j]=dp[0] [j-2] And p[j-1] = ‘*’： First line s Is an empty string , So when p Can be matched only by the even bits of .
• Return value dp[m] [n]

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));
        dp[0][0]=true;
        for(int i=2;i<=n;i++){
            dp[0][i]=dp[0][i-2]&&p[i-1]=='*';
        }

        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                dp[i][j]=p[j-1]=='*'?dp[i][j-2]||(dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.')):(dp[i-1][j-1]&&(s[i-1]==p[j-1]||p[j-1]=='.'));
            }
        }
        return dp[m][n];
    }
};

Time complexity O(mn)

Spatial complexity O(mn)