Regular Expression Matching 154

Question

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", "cab") → true

Solution

这道题和Wildcard Match有相似，但是又不同。在wildcard match中，“ ”表示的是可以和任意字符串进行匹配，而在这道题中“ ”表示的是可以取任意多个其之前的字符，比如“a ” 就表示“ ”可以取任意多个“a”，例如0个（“”），1个（“a”），2个（“aa”）...。但是，这道题也可以用DP来解决，而且思想和wildcard match非常相似。

match[i][j]表示s中前i个字符能否和p中前j个字符匹配。

初始化：

match[0][0] = true
match[0][j] = (p.charAt(j - 1) == '*' && match[0][j - 2])

即如果p中第j位是“ * ”，则对第j-1位的字符取0个（即第j-1到第j位字符看作“”），所以match[0][j]=match[0][j-2]

状态函数：

如果p中第j位是“ . ”或者p中第j位和s中第i位相同
match[i][j] = match[i - 1][j - 1]

如果p中第j位是“ * ”，则要分情况讨论
1. 如果p中第j-1位和s中第i位不想等并且p中第j-1位不是“.”，则不能用p中j-1位和s中第i位匹配，必须将j-1位消掉，因此“*”取0个之前元素，match[i][j]=match[i][j-2]
2. 如果p中第j-1位和s中第i位想等或者p中第j-1位为“.”，则“*”可以有三种选择
1）“*”取0个之前元素，和1中一样，将第j-1位消掉，让j-2位去和i位匹配（“”），match[i][j]=match[i][j-2]
2）“*”取1个之前元素，让j-1位和i位匹配，match[i][j]=match[i][j-1]
3）“*”取多个之前元素，因为i位一定会被匹配掉，因此看i-1位能否继续匹配，match[i][j]=match[i-1][j]
三种情况有一种为true则match[i][j]为true

代码如下：

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null){
            return false;
        }

        int n = s.length();
        int m = p.length();
        boolean[][] match = new boolean[n + 1][m + 1];
        match[0][0] = true;

        for(int i = 1; i <= n; i++){
            match[i][0] =false;
        }

        for(int j = 2; j <= m; j++){
            match[0][j] = (p.charAt(j - 1) == '*' && match[0][j - 2]);
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)){
                    match[i][j] = match[i - 1][j - 1];
                }

                if(p.charAt(j - 1) == '*' && j > 1){
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.'){
                        match[i][j] = match[i][j - 2];
                    }else{
                        match[i][j] = (match[i][j - 2] || match[i][j - 1] || match[i - 1][j]);
                    }
                }
            }
        }

        return match[n][m];
    }
}