Day 76, #10, Regular Expression Matching

Regular Expression Matching
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

 ------------------------------------------------------------------------------
Solution #1, recursion

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') {
            return *s == '\0';
        }
        
        if (*(p + 1) != '*') {
            return (*s == *p || (*p == '.' && *s != '\0')) && isMatch(s + 1, p + 1);
        }

        while (*p == *s || (*p == '.' && *s != '\0')) {
            if (isMatch(s,p + 2)) {
                return true;
            }
            s++;
        }
        return isMatch(s,p + 2);
    }
};

Solution #2, DP
dp[i][j] has the boolean value whether p[0 : i] can match s[0 : j], dp[0][0] is set to true since empty string matches empty pattern

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(p);
        int n = strlen(s);
        
        vector<vector<bool> > dp(m + 1,vector<bool>(n + 1,false));
        dp[0][0] = true;
        
        for (int i = 2; i <= m; i++) {
            if (p[i - 1] == '*' && dp[i - 2][0]) {
                dp[i][0] = true;
            }
        }
        
        for (int i = 1; i <= m; i++) {
            
            for (int j = 1; j <= n; j++) {
                if (p[i - 1] == s[j - 1] || p[i - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }else if (p[i - 1] == '*') {
                    // 1 or more char
                    if (dp[i][j - 1] && (p[i - 2] == s[j - 1] || p[i - 2] == '.')) {
                        dp[i][j] = true;
                    }
                    // zero char
                    else if (i - 2 >= 0 && dp[i - 2][j]) {
                        dp[i][j] = true;
                    }
                }
            }
            
        }
        
        return dp[m][n];
    }
};

class Solution {
public:
    bool helper(string s,string p,int i,int j) {
        if (j == p.length()) return i == s.length();
        
        if (j == p.length() - 1 || (j + 1 < p.length() && p[j + 1] != '*')) {
            if (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
                return helper(s,p,i + 1,j + 1);
            }
            return false;
        }
        
        while (i < s.length() && (p[j] == s[i] || p[j] == '.')) {
            if (helper(s,p,i,j + 2)) {
                return true;
            }
            i++;
        }
        return helper(s,p,i,j + 2);
    }
    
    bool isMatch(string s, string p) {
        return helper(s,p,0,0);
    }
};

Java
关键：把下一个 == '*' 和 != '*' 两种情况分开处理

class Solution {
    public boolean isMatch(String s, String p) {
        return rec(s,p,0,0);
    }
    
    private boolean rec(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) {
            return true;
        }
        
        if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
            int temp = i;
            while (temp < s.length() && (s.charAt(temp) == p.charAt(j) || p.charAt(j) == '.')) {
                if (rec(s, p, temp + 1, j + 2)) return true;
                temp++;
            }
            return rec(s,p,i,j + 2); // '*' matches zero chars
        }
        
        if (i < s.length() && j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.')) {
            return rec(s, p, i + 1, j + 1);
        }
    
        return false;
    }
}

预处理的时候要回头看2位之前的位置。
主函数中还要考虑'*' match 0个的情况

class Solution {
    public boolean isMatch(String s, String p) {
        List<List<Boolean>> dp = getDP(s, p);
        int m = p.length();
        int n = s.length();
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <=n; j++) {
                if (p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '.') {
                    dp.get(i).add(j, dp.get(i - 1).get(j - 1));
                } else if (p.charAt(i - 1) == '*') {
                    if (i - 2 >= 0 && dp.get(i - 2).get(j)) {
                        dp.get(i).add(j, true);
                    }else if (dp.get(i).get(j - 1) && (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.')) {
                        dp.get(i).add(j, true);
                    }
                }
            }
        }
        
        return dp.get(m).get(n);
    }
    
    private List<List<Boolean>> getDP(String s, String p) {
        int m = p.length();
        int n = s.length();
        List<List<Boolean>> dp = new ArrayList<>();
        
        for (int i = 0; i <= m; i++) {
            List<Boolean> list = new ArrayList<>();
            if (i == 0 || (p.charAt(i - 1) == '*' && dp.get(i - 2).get(0))) list.add(true);
            else list.add(false);
            for (int j = 0; j < n; j++) {
                list.add(false);
            }
            dp.add(list);
        }
        
        return dp;
    }
}