LeetCode 10 - 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:

Dynamic Programming.

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    if(n==0) return m==0;
    boolean[][] f = new boolean[m+1][n+1];
    f[0][0] = true;
    for(int j=2; j<=n; j++) {
        if(p.charAt(j-1)=='*') {
            f[0][j] = f[0][j-2];
        }
    }
    for(int i=1; i<=m; i++) {
        for(int j=1; j<=n; j++) {
            char cp = p.charAt(j-1);
            char cs = s.charAt(i-1);
            if(cp == '*') {
                char cp2 = p.charAt(j-2);
                if(cp2 == cs ||cp2 == '.') {
                    f[i][j] = f[i][j-2] || f[i-1][j];
                } else {
                    f[i][j] = f[i][j-2];
                }
            } else {
                if(cp == cs || cp == '.') {
                    f[i][j] = f[i-1][j-1];
                }
            }
        }
    }
    return f[m][n];
}

 

Solution 2:

Backtracking.

public boolean isMatch(String s, String p) {
    int sLen = s.length();
    int pLen = p.length();
    if(pLen == 0) {
        return sLen == 0;
    }
    char c = p.charAt(0);
    if(pLen == 1 || p.charAt(1) != '*') { //p is without *, i.e. ab
        if(sLen == 0 || (c != '.' && c != s.charAt(0))) {
            return false;
        } else {
            return isMatch(s.substring(1), p.substring(1));
        }
    } else { // p is with *, i.e. a*b
        int i=-1;
        while(i<sLen && (i<0 || c == '.' || c == s.charAt(i))) {
            if(isMatch(s.substring(i+1), p.substring(2))) {
                return true;
            }
            i++;
        }
    }
    return false;
}

又重构了下递归的代码：

public boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    if(n == 0) return m==0;
    char c = p.charAt(0);
    if(n==1 || p.charAt(1) != '*') { // p has no *
        if(m == 0 || s.charAt(0) != c && c != '.') return false;
        return isMatch(s.substring(1), p.substring(1));
    } else { // p has *
        int i = -1;
        do {
            if(isMatch(s.substring(++i), p.substring(2))) return true;
        } while(i<m && (c=='.' || s.charAt(i)==c));
    }
    return false;
}

 

C语言的代码更加简洁：

bool isMatch(char* s, char* p) {
    if(!*p) return !*s;
    if(p[1] != '*') {
        if(!*s || *s != *p && *p != '.') return false;
        return isMatch(s+1, p+1);
    } else {
        int i = -1;
        do {
            if(isMatch(++i+s, p+2)) return true;
        } while(s[i] && (s[i]==*p || *p=='.'));
    }
    return false;
}

 

或者这样：

bool isMatch(const char *s, const char *p) {
    if(!*p) return !*s;
    if(*(p+1) != '*') {
        if(!*s || *s != *p && *p != '.') return false;
        return isMatch(s+1, p+1);
    } else {
        int i = -1;
        do {
            if(isMatch(++i+s, p+2)) return true;
        } while(*(s+i) && (*(s+i)==*p || *p=='.'));
    }
    return false;
}

 

Reference:

http://leetcode.com/2011/09/regular-expression-matching.html