题设
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()];
}
