Regular Expression Matching

• Lintcode : 154 / Leetcode : 10
• Level : Hard

Problem

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(string s, string p)

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

Example
Example 1:

Input："aa"，"a"
Output：false
Explanation：
unable to match
Example 2:

Input："aa"，"a*"
Output：true
Explanation：
'*' can repeat a

Concept & Algorithm

筆記-1
筆記-2

Time Complexity & Space Complexity

time : O()
space: O()

Answer

class Solution {
public:
    bool isMatch(string &s, string &p) {
        int n = s.size(), m = p.size();
        vector<vector<bool>> isVisited(n, vector<bool>(m, false));
        vector<vector<bool>> memo(n, vector<bool>(m, false));
        return dfs(s, p, 0, 0, isVisited, memo);
    }
private:
    bool dfs(string &s, string &p, int sIndex, int pIndex, vector<vector<bool>> &isVisited, vector<vector<bool>> &memo) {
        if (sIndex == s.size() && pIndex == p.size()) return true;
        if (pIndex == p.size()) return false;
        if (sIndex == s.size()) {
            if (p.size() - pIndex == 1 || (p.size() - pIndex) % 2) return false;
            for (int i = pIndex + 1; i < p.size(); i += 2) {
                if (p[i] != '*') return false;
            }
            return true;
        }
        if (isVisited[sIndex][pIndex]) return memo[sIndex][pIndex];
        bool normal = false, left = false, center = false, right = false;
        if (s[sIndex] == p[pIndex] || p[pIndex] == '.') {
            normal = dfs(s, p, sIndex + 1, pIndex + 1, isVisited, memo);
        }
        if (pIndex + 1 < p.size() && p[pIndex + 1] == '*') {
            if (p[pIndex] == s[sIndex] || p[pIndex] == '.') {
                center = dfs(s, p, sIndex, pIndex + 2, isVisited, memo);
                right = dfs(s, p, sIndex + 1, pIndex, isVisited, memo);
            }else {
                left = dfs(s, p, sIndex, pIndex + 2, isVisited, memo);
            }
        }
        isVisited[sIndex][pIndex] = true;
        return memo[sIndex][pIndex] = normal || left || center || right;
    }
};

tags: DP

​