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) Java

Recursive call, the end condition is both s and p are empty (either null or 0 length). The match first considers '*', then '.' or same char. In '*' case, consider no match or one/more match

   public boolean isMatch(String s, String p) {
        if ((p == null || p.length() == 0) && (s != null && s.length() > 0)) {
            return false;
        }
        if ((p == null && s == null) || (p.length() == 0 && s.length() == 0)) {
            return true;
        }
        if (s == null || p == null) {
            return false;
        }
        if (s.length() == 0 && p.length() > 1 && p.charAt(1) == '*') {
            return isMatch(s, p.substring(2));
        } else if (s.length() == 0 && p.length() >= 1) {
            return false;
        }
        if (p.length() > 1 && p.charAt(1) == '*') {
            if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') {
                return isMatch(s.substring(1), p) || isMatch(s, p.substring(2));
            } else {
                return isMatch(s, p.substring(2));
            }
        }
        if (p.charAt(0) == '.' || p.charAt(0) == s.charAt(0)) {
            return isMatch(s.substring(1), p.substring(1));
        }
        return false;
    }

(2) Python

关键在于当碰到“*”时，只要考虑（1）不匹配，p要倒退2个字符，s不动（2）一个或多个匹配，p不动，s退一个字符。

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False for x in xrange(len(s)+1)] for y in xrange(len(p)+1)]
        dp[0][0] = True
        for i in xrange(2, len(p)+1):
            if p[i-1] == '*':
                dp[i][0] = dp[i-2][0]
        for i in xrange(1, len(p)+1):
            for j in xrange(1, len(s)+1):
                if i>1 and p[i-1]=='*':
                    if p[i-2]=='.' or p[i-2]==s[j-1]:
                        dp[i][j] = dp[i][j-1] | dp[i-2][j]
                    else:
                        dp[i][j] = dp[i-2][j]
                elif p[i-1]=='.' or p[i-1]==s[j-1]:
                    dp[i][j] = dp[i-1][j-1]
        return dp[len(p)][len(s)]

(3) Scala

object Solution {
    def isMatch(s: String, p: String): Boolean = {
        if (s.length() == 0 && p.length() == 0) {
            return true
        }
        if (p.length() == 0 && s.length() != 0) {
            return false
        }
        if (s.length() == 0 && (p.length() == 1 || p.charAt(1) != '*')) {
            return false
        }
        if (p.length() > 1 && p.charAt(1) == '*') {
            if (s.length() == 0 || (s.charAt(0) != p.charAt(0) && p.charAt(0) != '.')) {
                return isMatch(s, p.substring(2))
            } else if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') {
                return isMatch(s, p.substring(2)) || isMatch(s.substring(1), p) || isMatch(s.substring(1), p.substring(2))
            } 
        } else if (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') {
            return isMatch(s.substring(1), p.substring(1))
        }
        return false
    }
}

dp version:

object Solution {
    def isMatch(s: String, p: String): Boolean = {
        val dp = Array.ofDim[Boolean](s.length()+1,p.length()+1)
        dp(0)(0) = true
        for (k <- 2 to p.length()) {
            if (p.charAt(k-1) == '*') {
                dp(0)(k) = dp(0)(k-2)
            }
        }
        for (i <- 1 to s.length()) {
            for (j <- 1 to p.length()) {
                if (j > 1 && p.charAt(j-1) == '*') {
                    if (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.') {
                        dp(i)(j) = dp(i)(j-2) || dp(i-1)(j) || dp(i-1)(j-2) // it seems || dp(i-1)(j-2) does not matter
                    } else {
                        dp(i)(j) = dp(i)(j-2)
                    }
                } else if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.') {
                    dp(i)(j) = dp(i-1)(j-1)
                }
            }
        }
        return dp(s.length())(p.length())
    }
}