Regular Expression Matching

Source

• leetcode: Regular Expression Matching

'.' 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

Java

public class Solution {
    public boolean isMatch(String s, String p) {
        return isMatchHelper(s, 0, p, 0);   
    }  

    private boolean isMatchHelper(String s, int i, String p, int j) {    
        if (p.length() == j) return (s.length() == i);    

        // next char is not '*': do current char match?    
        if (j == p.length() - 1 || p.charAt(j+1) != '*') {    
            if (s.length() == i) return false;    
            return (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)) && isMatchHelper(s, i+1, p, j+1);    
        }   

        // next char is '*'    
        // one or more    
        while (i < s.length() && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j))) {    
            if (isMatchHelper(s, i, p, j+2)) return true;    
            i++;    
        }    

        // zero    
        return isMatchHelper(s, i, p, j+2);    
    }  
}

/**
 -- dp[s.length() + 1][p.length() + 1], where dp[i][j] means the first i characters from string i matches the first j characters in string j. 
 -- Initial state: dp[0][0] = true, e.g. "" -> "", true. 
                   dp[i][0] = false, i >= 1, any string cannot match a empty string 
                   dp[0][i], if (p.charAt(j) == '*'), dp[0][j] = dp[0][j - 2] 

-- Transit function: 
      -- If p.charAt(j) != '*'. Then IF s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.'. 
            -- dp[i][j] = dp[i - 1][j - 1];
      -- Else  // p.charAt(j - 1) == "*"
           -- If s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.' 
               Then dp[i][j] = dp[i][j - 2] // zero matched, e.g. s = acdd, p = acb*dd. 
           -- Else 
                Then dp[i][j] = dp[i][j - 2]  ||  // zero matched
                                       dp[i][j - 1] || // 1 matched
                                       dp[i - 1][j] // 2+ matched
*/

//DP
public class Solution {
    public boolean isMatch(String s, String p) {

        if (p == null || p.length() == 0) {
            return s == null || s.length() == 0;
        }
        int rows = s.length();
        int cols = p.length();

        boolean[][] dp = new boolean[rows + 1][cols + 1];
        dp[0][0] = true;

        for (int j = 1; j <= cols; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                char sChar = s.charAt(i - 1);
                char pChar = p.charAt(j - 1);

                if (pChar != '*') {
                    if (sChar == pChar || pChar == '.') {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    if (sChar != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j] || dp[i][j - 1];
                    }
                }
            }
        }
        return dp[rows][cols];
    }  
}

Reference

Regular Expression Matching