Regular Expression Matching Solutions in C++

// Source : https://oj.leetcode.com/problems/regular-expression-matching/
// Author : Hao Chen
// Date   : 2014-08-24



#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;


bool isMatch(const char *s, const char *p) {

    if (*p=='\0') {
        return *s == '\0';
    }
    //p's length 1 is special case 
    if (*(p+1) == '\0' || *(p+1) !='*' ) {
        if (*s=='\0' || ( *p !='.' && *s != *p )) {
            return false;
        }
        return isMatch(s+1, p+1);
    }
    int len = strlen(s);
    int i = -1;
    while (i < len && (i <0 || *p=='.' || *p==*(s+i)) ){
        if (isMatch(s+i+1, p+2)) {
            return true;
        }
        i++;
    }
    return false;
}


int main(int argc, char** argv)
{
    const char* s = "aaa";
    const char* p = "a.*";

    if (argc>2) {
        s = argv[1];
        p = argv[2];
    }

    cout << s << ", " << p << " : " << isMatch(s,p) << endl;
}

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        for (char c=*p; c != '\0'; ++s, c=*p) {
            if (p[1] != '*') ++p;
            else if (isMatch(s, p+2)) return true;
            if (!(c == *s || (c == '.' && *s != '\0'))) return false;
        }
        return *s == '\0';
    }
};

/// Source : https://leetcode.com/problems/regular-expression-matching/
/// Author : liuyubobobo
/// Time   : 2019-03-19

#include <iostream>
#include <vector>

using namespace std;


/// DFS
/// Time Complexity: O((s + p) * 2^(s + p))
/// Space Complexity: O(s + p)
class Solution {
public:
    bool isMatch(const string& s, const string& p) {
        return match(s, 0, p, 0);
    }

private:
    bool match(const string& s, int sl, const string& p, int pl){

        if(sl == s.size()) return no_more_match(p, pl);
        if(pl == p.size()) return false;

        if(pl + 1 < p.size() && p[pl + 1] == '*'){
            if(s[sl] == p[pl] || p[pl] == '.')
                return match(s, sl + 1, p, pl) || match(s, sl, p, pl + 2);
            else
                return match(s, sl, p, pl + 2);
        }
        else if(s[sl] == p[pl] || p[pl] == '.')
            return match(s, sl + 1, p, pl + 1);
        return false;
    }

    bool no_more_match(const string& p, int pl){
        int i;
        for(i = pl; i < p.size(); i += 2)
            if(i + 1 < p.size() && p[i + 1] != '*') return false;
        return i == p.size();
    }
};


int main() {

    cout << Solution().isMatch("aa", "a") << endl; // false
    cout << Solution().isMatch("aa", "a*") << endl; // true
    cout << Solution().isMatch("ab", ".*") << endl; // true
    cout << Solution().isMatch("aab", "c*a*b") << endl; // true
    cout << Solution().isMatch("mississippi", "mis*is*p*") << endl; // false
    cout << Solution().isMatch("ab", ".*c") << endl; // false
    cout << Solution().isMatch("a", ".*..a") << endl; // false
    cout << Solution().isMatch("", ".*") << endl; // true

    return 0;
}

/// Source : https://leetcode.com/problems/regular-expression-matching/
/// Author : liuyubobobo
/// Time   : 2019-03-19

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(s * p)
/// Space Complexity: O(s * p)
class Solution {
public:
    bool isMatch(const string& s, const string& p) {

        vector<vector<int>> dp(s.size(), vector<int>(p.size(), -1));
        return match(s, 0, p, 0, dp);
    }

private:
    bool match(const string& s, int sl, const string& p, int pl,
               vector<vector<int>>& dp){

        if(sl == s.size()) return no_more_match(p, pl);
        if(pl == p.size()) return false;

        if(dp[sl][pl] != -1) return dp[sl][pl];

        if(pl + 1 < p.size() && p[pl + 1] == '*'){
            if(s[sl] == p[pl] || p[pl] == '.')
                return dp[sl][pl] = (match(s, sl + 1, p, pl, dp) || match(s, sl, p, pl + 2, dp));
            else
                return dp[sl][pl] = match(s, sl, p, pl + 2, dp);
        }
        else if(s[sl] == p[pl] || p[pl] == '.')
            return dp[sl][pl] = match(s, sl + 1, p, pl + 1, dp);
        return dp[sl][pl] = false;
    }

    bool no_more_match(const string& p, int pl){
        int i;
        for(i = pl; i < p.size(); i += 2)
            if(i + 1 < p.size() && p[i + 1] != '*') return false;
        return i == p.size();
    }
};


int main() {

    cout << Solution().isMatch("aa", "a") << endl; // false
    cout << Solution().isMatch("aa", "a*") << endl; // true
    cout << Solution().isMatch("ab", ".*") << endl; // true
    cout << Solution().isMatch("aab", "c*a*b") << endl; // true
    cout << Solution().isMatch("mississippi", "mis*is*p*") << endl; // false
    cout << Solution().isMatch("ab", ".*c") << endl; // false
    cout << Solution().isMatch("a", ".*..a") << endl; // false
    cout << Solution().isMatch("", ".*") << endl; // true

    return 0;
}