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
思路：如果下个字符是'*'，那么可以重复当前字符0,1,2...次=>带回溯的递归。O(n)=kn，k是*出现的次数。
class Solution {
public:
bool isMatch(string s, string p) {
return dfsIsMatch(s,p,0,0);
}
bool dfsIsMatch(const string& s, const string& p, int sIndex, int pIndex){
if (p[pIndex] == ' ') //结束条件：s若是' '，p必须也是' '
return s[sIndex] == ' ';
if (p[pIndex+1] == '*') {
/* '.' means any character (except ' ')
* '.' means repeat 0 or more times
* '.*' means repeat '.' 0 or more times
*/
while ((s[sIndex] != ' ' && p[pIndex] == '.') || s[sIndex] == p[pIndex]) { //'.'可以与除' '以外的任何字符匹配
if (dfsIsMatch(s, p, sIndex, pIndex+2)) //p[pIndex] repeat 0 times
return true;
sIndex += 1;//p[pIndex]在原基础上repeat次数+1
}
return dfsIsMatch(s, p, sIndex, pIndex+2); //when s[sIndex] != p[pIndex] && p[pIndex] != '.'(此时只有s[sIndex]==p[pIndex]==' '时可能return true)
}
else if ((s[sIndex] != ' ' && p[pIndex] == '.') || s[sIndex] == p[pIndex]) {
return dfsIsMatch(s, p, sIndex + 1, pIndex + 1);
}
return false;
}
};
法II：动态规划。设二位数组dp[i][j]来表示两个string的状态关系，dp[i][j]=true，表示s[0..i-1]匹配p[0..j-1]的结果。O(n)=n2
dp的下标0表示NULL，设置的原因是，比方如果p的第二个字符是*，那么p可以从第三个字符开始与s的第一个字符匹配，也就是dp[0][2]=true。
class Solution {
public:
bool isMatch(string s, string p) {
int sLen=s.length();
int pLen = p.length();
bool dp[sLen+1][pLen+1]={false}; //[0]for string NULL
//initialize
dp[0][0]=true;
for(int j = 1; j <= pLen; j++){
dp[0][j]=j>=2 && dp[0][j-2] && p[j-1]=='*'; //* each other letter
}
//state transfer
for(int i = 1; i <= sLen; i++){
for(int j = 1; j <= pLen; j++){
if(p[j-1]=='*'){
dp[i][j]=(j>=2 && dp[i][j-2])/* repeat 0 times*/
||(dp[i][j-1])/*repeat 1 time*/
||(j>=2 && (s[i-1]==p[j-2] || p[j-2]=='.') && dp[i-1][j])/*repeat several times*/;
}
else{ //p[j-1]!='*'
dp[i][j]=dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
}
}
}
return dp[sLen][pLen];
}
};