LeetCode 10. Regular Expression Matching

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:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-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
解析：
此题目为正则匹配的题目，这里.可以匹配任意字符，*匹配前面一个字符0次或者多次。
解法1:
递归法，采用深度优先搜索，从前往后进行匹配处理。
参考自：https://www.cnblogs.com/grandyang/p/4461713.html
https://www.bilibili.com/video/av63859909/
若p为空，若s也为空，返回 true，反之返回 false。
若p的长度为1，若s长度也为1，且相同或是p为 ‘.’ 则返回 true，反之返回 false。
若p的第二个字符不为*，若此时s为空返回 false，否则判断首字符是否匹配，且从各自的第二个字符开始调用递归函数匹配。
若p的第二个字符为*，进行下列循环，条件是若s不为空且首字符匹配（包括 p[0] 为点），调用递归函数匹配s和去掉前两个字符的p（这样做的原因是假设此时的星号的作用是让前面的字符出现0次，验证是否匹配），若匹配返回 true，否则s去掉首字母（因为此时首字母匹配了，我们可以去掉s的首字母，而p由于星号的作用，可以有任意个首字母，所以不需要去掉），继续进行循环。
代码如下：
[cc lang=”C++”]
class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty()) return s.empty();
if (p.size() == 1) {
return (s.size() == 1 && (s[0] == p[0] || p[0] == ‘.’));
}
if (p[1] != ‘*’) {//第2个字符不是*，先看看s,p第一个字符是否匹配，然后分别去掉首字符，匹配剩余内容
if (s.empty()) return false;
return (s[0] == p[0] || p[0] == ‘.’) && isMatch(s.substr(1), p.substr(1));
}
while (!s.empty() && (s[0] == p[0] || p[0] == ‘.’)) {//第一个字母匹配，p的第二个字符是*
if (isMatch(s, p.substr(2))) return true;//确认a*是否出现0次
s = s.substr(1);//否则*需要出现1到多次，去掉已经匹配的s的首字母，把剩余内容进行匹配
}
return isMatch(s, p.substr(2));
}
};
[/cc]
运行结果：

解法2:
动态规划法
参考自：https://leetcode.com/problems/regular-expression-matching/discuss/5651/Easy-DP-Java-Solution-with-detailed-Explanation
对于每个情况进行分析，用dp[i][j]表示s[0到i]和p[0到j]是否匹配。
情况划分如下：
1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
这种情况对应于s=aa,p=aa
2, If p.charAt(j) == ‘.’ : dp[i][j] = dp[i-1][j-1];
这种情况对应于s=aa,p=a.
3, If p.charAt(j) == ‘*’:
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
这种情况下a*出现零次，比如s=aab,p=c*a*b*，c*出现0次。
2 if p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == ‘.’:
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty

代码如下：
[cc lang=”C++”]
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector>dp (m +1,vector(n+1));
dp[0][0] = true;
//预处理阶段，针对s=ab,p=c*ab 这种*出现0次的情况，处理匹配空串的情况
//处理pattern匹配空串的情况，因为后面代码里面处理不到这部分内容
for(int i = 0; i < p.size(); i++) { if(p[i] == '*' && dp[0][i-1]) dp[0][i+1] = true; } for(int i =0; i < m; i++) { for(int j =0; j < n; j++) { if(p[j] == '.') dp[i+1][j+1] = dp[i][j]; if(p[j] == s[i]) dp[i+1][j+1] = dp[i][j]; if(p[j] == '*') { if(s[i] != p[j-1] && p[j-1] != '.') dp[i+1][j+1] = dp[i+1][j-1]; else{ dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]); } } } } return dp[m][n]; } }; [/cc] 运行结果：
解法3:
动态规划
参考自：https://leetcode.com/problems/regular-expression-matching/discuss/5684/c-on-space-dp
将解法2中的一些情况进行合并。
1. dp[i][j] = dp[i – 1][j – 1], if p[j – 1] != ‘*’ && (s[i – 1] == p[j – 1] || p[j – 1] == ‘.’);
2. dp[i][j] = dp[i][j – 2], if p[j – 1] == ‘*’ and the pattern repeats for 0 time;
3. dp[i][j] = dp[i – 1][j] && (s[i – 1] == p[j – 2] || p[j – 2] == ‘.’), if p[j – 1] == ‘*’ and the pattern repeats for at least 1 time.

代码如下：
[cc lang=”C++”]
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')); } else { dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.'); } } } return dp[m][n]; } }; [/cc] 参考： https://www.youtube.com/watch?v=c5vsle60Uw8