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

要点

• 二维数组动态规划DP[][]

首先，按照之前解回文串的思路，这种题可以考虑采用动态规划的方法来做。我们用DP[i][j]表示s[0->(i-1)]与p[0->(j-1)]是否匹配。
如果s、p为null，返回false。注意这里不能s.length=0或p.length=0就返回false，因为""可以和".*"匹配的。

初始化DP[0][0]=true，代表s、p都为空串。然后进行初始化。初始化过程中运用到的递推公式为：

DP[0][j-1] = true && p.charAt(j) = '*'，则DP[0][j+1] = true。即前j-1个字符串可以形成空串，且第j个字符为'*'。则前j个字符串也可以形成空串。

DP[i][0]的初始化方法相同。

然后，考虑s、p都非空的情况。递推公式有：

if(s.charAt(i) == p.charAt(j) || p.charAt(j) = '.')，即s的第i位与p的第j位可以匹配。
则如果s的前i-1位与p的前j-1位匹配，就有s的前i位与p的前j位匹配。即：DP[i+1][j+1] = DP[i][j]

if(p.charAt(j) == '*')如果P[j] = '*'，那么需要继续分情况讨论。注意第一位不会是*，所以此时有j>=1
    1、p.charAt(j - 1) != s.charAt(i) && p.charAt(j - 1) != '.'
        这种情况下，x*只能转化为空，才有可能匹配。匹配成立的条件是DP[i+1][j+1] = DP[i+1][j-1]，x*转化为空，往前挪2位；
    2、p.charAt(j - 1) == s.charAt(i) || p.charAt(j - 1) == '.'
        这种情况下，x*可以为空、可以为x、可以为≥2个x，分类讨论：
        2.1、x*为空。则与1相同，DP[i+1][j+1] = DP[i+1][j-1]，x*转化为空，往前挪2位；
        2.2、x*=x，则DP[i+1][j+1] = DP[i+1][j]；
        2.3、x*=xx...x。这种情况下，如果s删掉最后一位后匹配，则匹配(x*再补出最后一位即可)。有DP[i+1][j+1] = DP[i][j+1]。

代码：

   public static boolean isMatch(String s , String p){
        if(s == null  || p == null) // 注意s=""的时候，p=".*"这样是可以匹配的！
            return false;
        boolean DP[][] = new boolean[s.length() + 1][p.length() + 1]; // DP[i][j]代表S[0,1,2,..,i-1]与P[0,1,2,...,j-1]是否匹配
        DP[0][0] = true;
        for(int j = 1;j < p.length();j++){
            if(DP[0][j - 1] && p.charAt(j) == '*') // 递推公式：P[0,j-1]可以为空，且P[j] = '*'，则P[0 , j]可以为空
                DP[0][j + 1] = true;
            else
                DP[0][j + 1] = false;
        }
        for(int i = 1;i < s.length();i++){
            if(DP[i - 1][0] && s.charAt(i) == '*') // 同理
                DP[i + 1][0] = true;
        }

        for(int i = 1;i <= s.length();i++){
            for(int j = 1;j <= p.length();j++){
                if(s.charAt(i - 1) == p.charAt(j - 1)){ // S[i-1]=P[j-1]，则DP[i][j] = DP[i-1][j-1]
                    DP[i][j] = DP[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '.') // P[j-1]='.'，匹配任何字符，则DP[i][j] = DP[i-1][j-1]
                    DP[i][j] = DP[i - 1][j - 1];
                /*
                如果P[j - 1] = '*'，那么需要继续分情况讨论。注意第一位不会是*，所以此时有j>=2
                    1、如果P[j-2] != S[i-1]且P[j-2] != '.'，则x*需要为0个，此时DP[i][j] = DP[i][j - 2]
                    2、如果P[j-2] == S[i-1]或P[j - 2] == '.'，分3类讨论：
                        2.1、x*为0个，则有DP[i][j] = DP[i][j - 2]
                        2.2、x*为1个，则有DP[i][j] = DP[i][j - 1]
                        2.3、x*为多个，这种情况下，如果s删掉最后一位后匹配，则匹配(x*再补出最后一位即可)。即DP[i][j] = DP[i-1][j]

                */

                if(p.charAt(j - 1) == '*'){
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.')
                        DP[i][j] = DP[i][j - 2];
                    else{
                        DP[i][j] = (DP[i][j - 2] || DP[i][j - 1] || DP[i - 1][j]);
                    }
                }
            }
        }
        for(int i = 0;i <= s.length();i++){
            for(int j = 0;j < p.length();j++){
                System.out.print(DP[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("--------------");
        return DP[s.length()][p.length()];


    }