Given an input string (s) and a pattern (p), 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).
Note:
-
scould be empty and contains only lowercase lettersa-z. -
pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false 题解：这个题如果用暴力的想法很难想清楚，因为对于.*的处理很难，但是如果我们理解.*可匹配也可不匹配这样一个性质就很容易联想递归或者DP的思路了：
这道题分的情况的要复杂一些，先给出递归的解法：
- 若p为空，且s也为空，返回true，反之返回false
- 若p的长度为1，且s长度也为1，且相同或是p为'.'则返回true，反之返回false
- 若p的第二个字符不为*，且此时s为空则返回false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配
- 若p的第二个字符为*，s不为空且字符匹配，调用递归函数匹配s和去掉前两个字符的p，若匹配返回true，否则s去掉首字母
- 返回调用递归函数匹配s和去掉前两个字符的p的结果
由于我对递归结束的判断实在是太恶心了。。。。于是时间和空间都很慢，不过因为是最好理解的思路，所以还是把代码扔上来：
class Solution {
public:
int in(char ch){
if(ch=='.') return ;
else if(ch=='*') return ;
else return ;
}
bool isMatch(string s, string p) {
int lens = s.length();int lenp = p.length();
if(lens== && lenp==) { return ;}
if(lens== && lenp== && s[]==p[]) {return ;}
if(lens== && lenp==) return ;
if(lens!= && lenp==) { return ;}
if(lens==){
if((in(p[])==&&in(p[])!=)||(in(p[])== &&in(p[])!=)) return ;
if(in(p[])==) return isMatch(s,p.substr(,lenp));
}
if(in(p[])==&&in(p[])!=){
if(lens==||p[]!=s[]) { return ;}
else return isMatch(s.substr(,lens),p.substr(,lenp));
}
if(in(p[])==&&in(p[])!=){
if(lens==) { return ;}
else return isMatch(s.substr(,lens),p.substr(,lenp));
}
if(in(p[])==&&in(p[])==){
if(p[]!=s[]) return isMatch(s,p.substr(,lenp));
else return max(isMatch(s.substr(,lens),p),isMatch(s,p.substr(,lenp)));
}
if(in(p[])==&&in(p[])==)
return max(isMatch(s.substr(,lens),p),isMatch(s,p.substr(,lenp)));
cout<<<<endl; return ;
}
};
后来在网上看到了大佬原来可以这么写
class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() > && p[] == '*') {
return isMatch(s, p.substr()) || (!s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p));
} else {
return !s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(), p.substr());
}
}
};
我们也可以用DP来解，定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况(下面部分摘自：https://leetcode.com/problems/regular-expression-matching/discuss/5684/9-lines-16ms-c-dp-solutions-with-explanations)：
1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3.
P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] ==
'.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + , vector<bool>(n + , false));
dp[][] = true;
for (int i = ; i <= m; ++i) {
for (int j = ; j <= n; ++j) {
if (j > && p[j - ] == '*') {
dp[i][j] = dp[i][j - ] || (i > && (s[i - ] == p[j - ] || p[j - ] == '.') && dp[i - ][j]);
} else {
dp[i][j] = i > && dp[i - ][j - ] && (s[i - ] == p[j - ] || p[j - ] == '.');
}
}
}
return dp[m][n];
}
};