Regular Expression Matching Demystified

Regular Expression Matching Series

leetcode44 Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’

‘?’ Matches any single character. ‘*’ Matches any sequence of characters (including the empty sequence).

bool isMatch(string s, string p) {
    // Remove duplicate * characters
    string tmp="";
    bool first=true;
    for(auto c : p) {
        if (c=='*') {
            if (first) {
                first=false;
                tmp.push_back(c);
            }
        } else {
            tmp.push_back(c);
            first=true;
        }
    }

    p=tmp;

    vector<vector<bool> > dp(s.size()+1, vector<bool>(p.size()+1, false));
    if (p.size()>0 && p[0]=='*') dp[0][1]=true;
    dp[0][0]=true;

    for(int i=1;i<dp.size();++i) {
        for(int j=1;j<dp[0].size();++j) {
            // ? or equal characters - result depends on previous strings
            if (p[j-1]=='?' || s[i-1]==p[j-1])
                dp[i][j]=dp[i-1][j-1];
            // Current is *, can consume one or none
            else if (p[j-1]=='*')
                dp[i][j]=dp[i][j-1] || dp[i-1][j];
        }
    }
    return dp[s.size()][p.size()];
}

leetcode10

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.

bool isMatch(string s, string p) {
    string tmp="";
    bool first=true;
    for(auto c : p) {
        if (c=='*') {
            if (first) {
                first=false;
                tmp.push_back(c);
            }
        } else {
            tmp.push_back(c);
            first=true;
        }
    }

    p=tmp;

    vector<vector<bool> > dp(s.size()+1, vector<bool>(p.size()+1, false));
    dp[0][0]=true;
    if (p.size()>0 && p[0]=='*') dp[0][1]=true;
    for(int i=2;i<dp[0].size();++i)
        if(p[i-1]=='*') dp[0][i]=dp[0][i-2];

    for(int i=1;i<dp.size();++i) {
        for(int j=1;j<dp[0].size();++j) {
            // Characters match or pattern is any character
            if((s[i-1]==p[j-1])||(p[j-1]=='.'))
                dp[i][j]=dp[i-1][j-1];
            else if (p[j-1]=='*') {
                // Check if character before * matches
                if ((s[i-1]==p[j-2])||(p[j-2]=='.'))
                    dp[i][j]=dp[i-1][j];
                // If * treats as empty string, check previous match
                if (j>1 && !dp[i][j]) dp[i][j]=dp[i][j-2];
            }
        }
    }
    return dp[s.size()][p.size()];
}

#DP

Reconstructing Binary Trees from Traversal Sequences Remove Duplicates from Sorted Arrays