LeetCode Regular Expression Matching

class Solution {
#define SINGLE 1
#define MULTIP 2
public:
    bool isMatch(const char *s, const char *p) {
        if (s == NULL || p == NULL) return true;
        
        vector<pair<char, int> > pattern;
        
        int     pos = 0;
        char     ch = '';
        
        while ((ch = p[pos++]) != '') {
            if (ch == '*') {
                pattern.back().second = MULTIP;
                continue;
            }
            pattern.push_back(make_pair(ch, SINGLE));
        }
        
        return isMatch(s, 0, pattern, 0);
    }
    
    bool isMatch(const char *s, int pos, vector<pair<char, int> > &pattern, int ppos) {
        if (ppos == pattern.size()) {
            return s[pos] == '';
        }
        int i = pos;
        pair<char, int> &p = pattern[ppos];

        int     offset = (p.second == SINGLE) ? 0 : -1;
        char     ch = '';
        while (offset < 0 || (ch = s[pos + offset]) != '') {
            if (offset >= 0 && !cmp(ch, p.first)) {
                return false;
            }
            if (isMatch(s, pos + offset + 1, pattern, ppos + 1)) {
                return true;
            }
            if (p.second == SINGLE) break;
            offset++;
        }
        return false;
    }
    
    bool cmp(const char a, const char b) {
        if (a == '.' || b == '.') return true;
        return a == b;
    }
};

暴力法, 216ms,

改写为记忆搜索,这里假设字符串和模式字符串的长度都不超过unsigned short 范围(6w+)， 84ms

class Solution {
#define SINGLE 1
#define MULTIP 2
private:
    unordered_map<unsigned int, bool> memo;
public:
    bool isMatch(const char *s, const char *p) {
        if (s == NULL || p == NULL) return true;
        memo.clear();
        
        vector<pair<char, int> > pattern;
        
        int     pos = 0;
        char     ch = '';
        
        while ((ch = p[pos++]) != '') {
            if (ch == '*') {
                pattern.back().second = MULTIP;
                continue;
            }
            pattern.push_back(make_pair(ch, SINGLE));
        }
        
        return isMatch(s, 0, pattern, 0);
    }
    
    bool isMatch(const char *s, int pos, vector<pair<char, int> > &pattern, int ppos) {
        unsigned int id = (pos << 16) | ppos;
        
        unordered_map<unsigned int, bool>::iterator iter = memo.find(id);
        if (memo.find(id) != memo.end()) return iter->second;
        
        bool res = false;
        
        if (ppos == pattern.size()) {
            res = s[pos] == '';
            memo.insert(make_pair(id, res));
            return res;
        }
        int i = pos;
        pair<char, int> &p = pattern[ppos];

        int     offset = (p.second == SINGLE) ? 0 : -1;
        char     ch = '';
        while (offset < 0 || (ch = s[pos + offset]) != '') {
            if (offset >= 0 && !cmp(ch, p.first)) {
                res = false;
                break;
            }
            if (isMatch(s, pos + offset + 1, pattern, ppos + 1)) {
                res = true;
                break;
            }
            if (p.second == SINGLE) break;
            offset++;
        }
        memo.insert(make_pair(id, res));
        return res;
    }
    
    bool cmp(const char a, const char b) {
        if (a == '.' || b == '.') return true;
        return a == b;
    }
};

第二轮：

Implement regular expression matching with support for '.' and '*'.

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

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

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

看到这样的题真有点写不下去，还是找了一发资料：

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (s == NULL || p == NULL) {
            return false;
        }
        if (*p == '') {
            return *s == '';
        }
        
        if (*(p+1) != '*') {
            return (*p == *s || (*p == '.' && *s != '')) && isMatch(s + 1, p + 1);
        }
        
        char curpat = *p;
        const char* sp = s;
        
        while (*sp == curpat || (curpat == '.' && *sp != '')) {
            if (isMatch(sp, p + 2)) {
                return true;
            }
            sp++;
        }
        return isMatch(sp, p + 2);
    }
};

 在discuss里找到一个dp解法：

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const int slen = strlen(s);
        const int plen = strlen(p);
        vector<vector<bool> > dp(slen+1, vector<bool>(plen+1, false));
        
        
        // when src string is empty, pattern string should be in form of
        // a*b*c*...
        for (int i=2; i<=plen; i+=2) {
            if (p[i-1] == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        dp[0][0] = true;
        
        for (int i=1; i<=slen; i++) {
            for (int j=1; j<=plen; j++) {
                if (s[i-1] == p[j-1] || p[j-1] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                    continue;
                }   
                if (p[j-1] == '*') {
                    if (p[j-2] == s[i-1] || p[j-2] == '.') {
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    } else {
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
        return dp[slen][plen];
    }
};