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
- 題目大意
實現(xiàn)一個判斷正則匹配的函數(shù)isMatch(s,p). 這個函數(shù)的第一個參數(shù)是要匹配的字符串s皮仁，第二個參數(shù)是正則表達式么库。
規(guī)則如下：
'.' 可以用來匹配人以單個字符
‘*’ 可以用來匹配0個或者多個上一個字符会傲。
除了使用效率較低的搜索算法兽埃，我們發(fā)現(xiàn)對于任意一個字符串侦鹏，前n個字符的匹配 和后面的字符沒有關系铜跑。所以我們可以用動態(tài)規(guī)劃解這道題湿右。 用match[i][j] 表示 字符串前i個字符 能否匹配 正則表達式前j個字符。
分情況討論：
match[i][j]=match[i-j][j-1] p[j]==s[i]
match[i][j]=match[i-j][j-1] p[j]!=s[i] && p[j]=='.'
match[i][j] = (match[i][j-1] || match[i-1][j] || match[i][j-2]) p[j]!=s[i] && p[j]=='*' && ( p[j-1]==s[i] || p[j-1]=='.')
match[i][j] = match[i][j-2] p[j]!=s[i] && p[j]=='*' && ( p[j-1]!=s[i] && p[j-1]!='.')
前1芜抒、2珍策、4情況都很好理解，下面舉例說明第3種情況宅倒。
s: XXXXXXa
p: XXXXa*
s字符串的a 的位置是i, p字符串*的位置是j攘宙。
當* 代表一個a 的時候 ：match[i][j-1]
當* 代表多個a的時候 ：match[i-1][j]
當* 代表空字符串的時候 ：match[i][j-2]
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s,p) {
let match=new Array(s.length+1);
for (let i=0;i<=s.length;i++){
let temp=new Array(p.length+1);
temp.fill(false);
match[i]=temp;
}
match[0][0] = true;
for (let i = 0; i < p.length; i++) {
match[0][i+1] = (p[i] == '*' && match[0][i-1]);
}
for (let i = 0 ; i < s.length; i++) {
for (let j = 0; j < p.length; j++) {
if (p[j] == '.') {
match[i+1][j+1] = match[i][j];
}
if (p[j] == s[i]) {
match[i+1][j+1] = match[i][j];
}
if (p[j] == '*') {
if (p[j-1] != s[i] && p[j-1] != '.') {
match[i+1][j+1] = match[i+1][j-1];
} else {
match[i+1][j+1] = (match[i+1][j] || match[i][j+1] || match[i+1][j-1]);
}
}
}
}
return match[s.length][p.length];
};
