[leetcode]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

算法思路：

二维动态规划，dp[i + 1][j + 1]表示字符串s(0~ i )和p(0~j)的匹配情况。

初始状态：dp[0][0] = true;

当s[i] == p[j] || p[j] == '.' 则dp[i][j] = dp[i - 1][j - 1]

当p[j] == '*'时：分两种情况：

1. s[i] != p[j - 2] && p[j - 2] != '.' 则dp[i][j] = dp[i][j - 2];

2. else dp[i][j] =  dp[i][j - 2] | dp[i - 1][j];

代码如下：

public class Solution {
    public boolean isMatch(String s, String p) {
            int height = s.length(),width = p.length();
            boolean[][] dp = new boolean[height + 1][width + 1];
            dp[0][0] = true;
            for(int i = 1; i <= width; i++){
                if(p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 2];
            }
            for(int i = 1; i <= height; i++){
                for(int j = 1; j <= width; j++){
                    char sChar = s.charAt(i - 1);                
                    char pChar = p.charAt(j - 1);
                    if(sChar == pChar || pChar == '.'){
                        dp[i][j] = dp[i - 1][j - 1];
                    }else if(pChar == '*'){
                        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];
                        }
                    }
                }
            }
            return dp[height][width];
        }
}