Sword finger offer 19 Regular Expression Matching

Original link ： The finger of the sword Offer 19. Regular Expression Matching

 

solution:

State means :dp[i][j] Express s Before i Can a character be the same as p Before j Characters match
Transfer equation :

        If s[i] == p[j] Express s Of the i Characters and p Of the j Two characters are the same , therefore dp[i][j] = dp[i - 1][j - 1].
        When p[j] == '.' When , because '.' Can represent any character, so dp[i][j] = dp[i - 1][j - 1].
         When p(j) == '*' when , if j>=2,dp[i][j]  It can be downloaded from dp[i][j - 2]   Transfer , It means to discard this time '*' And the character before it ; if i>0 And s[i] == p[j - 1], Indicates that this character can use this '*', You can from dp[i - 1][j] Transfer , Show utilization '*'.

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(),n = p.size();
        s = " " + s;
        p = " " + p;
        //dp[i][j] Express s Before i Characters and p Before j Whether the characters match 
        vector<vector<bool>> dp(m + 1, vector<bool> (n + 1, false));
        dp[0][0] = true;

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