Description
Implement regular expression matching with support for '.' and '*'.
Example
'.' 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次或多次
- 因为需要考虑前面的字符，所以从后往前匹配。
- 考虑 ''时的特殊情况，如果 ' '前面的字符和要匹配的一样，则分两张情况，即匹配0次或多次
- 如果不一样，则要匹配的不变，然后跳到*字符前面的前面。
- 没有说清楚，看代码吧
代码
class Solution {
public:
bool isMatch(string s, string p) {
int slen = s.size();
int plen = p.size();
return matchFunc(s, slen - 1, p, plen - 1);
}
bool matchFunc(string& s, int i, string &p, int j){
if(i < 0 && j < 0) return true;
if(i < 0 ) return p[j] == '*' ? matchFunc(s, i, p, j - 2) : false;
if(j < 0) return false;
if(s[i] == p[j] || p[j] == '.'){
return matchFunc(s, i - 1, p, j - 1);
}
else if(p[j] == '*'){
bool res = false;
//特殊情况
if(j - 1 >= 0){
if(p[j - 1] == '.' || p[j - 1] == s[i])
res = matchFunc(s, i - 1, p, j) || matchFunc(s, i - 1, p, j - 2);
}
return res || matchFunc(s, i, p, j - 2);
}
return false;
}
};动态规划
- 再讨论区里面还看到了一种动态规划的算法。在这里也作一个介绍，不得不感叹一句，大佬还是多呀。
- dp[i][j] 表示s[0..i)和p[0..j)的匹配结果，若为ture，则匹配，否则不匹配
- 则一共有以下状态：
- dp[i][j] = dp[i - 1][j - 1]，if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.')，注意下标的控制，dp[i][j]的下标是长度，而p[j-1]对应于dp[i][j]
- dp[i][j] = dp[i][j - 2], if p[j - 1] == '*', 且匹配0次
- dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')，此时p[j - 1] == '*' 且至少匹配一次
代码如下:
```cpp
class Solution {
public:
bool isMatch(string s, string p) {
int slen = s.size();
int plen = p.size();vector<vector<bool>> dp(slen + 1, vector<bool>(plen + 1, false)); dp[0][0] = true; for(int i = 0; i <= slen; ++i){ for(int j = 1; j <= plen; ++j){ if(p[j - 1] == '*'){ dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]); } else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); } } return dp[slen][plen]; }};
```
总结
- 递归往往可以改善的
- 向大佬学习！
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
