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
思路：
用二維數(shù)組記錄保存的狀態(tài)dp[lens+1][lenp+1]
dp[0][0] = true表示都為空枚粘，這種情況應(yīng)該返回false
1.s[i] == p[i] dp[i+1][j+1] = dp[i][j]
2.p[j] == '.' dp[i+1][j+1] = dp[i][j]
3.p[j] == ''
3.1.p[j-1] != '.' && p[j-1]!=s[i], dp[i+1][j+1] = dp[i+1][j-1] // a表示empty
3.2.
a:dp[i+1][j+1] = dp[i+1][j-1] // a表示empty
b:dp[i+1][j+1] = dp[i][j+1] // a表示多個
c:dp[i+1][j+1] = dp[i+1][j] // a表示一個欺抗，為什么是dp[i+1][j]---因為這個是最近的狀態(tài)
a,b,c取或设预，因為是一種情況蹬挤。
代碼：
public boolean isMatch(String s, String p) {
if(s == null || p == null)return false;
int lenS = s.length();
int lenP = p.length();
boolean[][] dp = new boolean[lenS + 1][lenP + 1];
dp[0][0] = true;
for(int j = 0;j < lenP;j++){
if(p.charAt(j) == '*' && dp[0][j-1]){ // p.charAt(0) != '*'
dp[0][j+1] = true;
}
}
for(int i=0;i<lenS;i++){
for(int j=0;j<lenP;j++){
if('.' == p.charAt(j)){
dp[i+1][j+1] = dp[i][j];
}
if(s.charAt(i) == p.charAt(j)){
dp[i+1][j+1] = dp[i][j];
}
if(p.charAt(j) == '*'){
if(p.charAt(j-1) != '.' && p.charAt(j-1) != s.charAt(i)){
dp[i+1][j+1] = dp[i+1][j-1]; // a*表示匹配空
}else {
dp[i+1][j+1] = (dp[i][j+1] || dp[i+1][j] || dp[i+1][j-1]); // 分別代表多個, 一個和空惨缆。
}
}
}
}
return dp[lenS][lenP];
}