19. 正则表达式匹配
1. 描述
请实现一个函数用来匹配包含'. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
2. 例子
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:
输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3:
输入:
s = “ab”
p = “.”
输出: true
解释: “.” 表示可匹配零个或多个（'*'）任意字符（’.'）。
示例 4:
输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:
s = “mississippi”
p = “misisp*.”
输出: false
3. 说明
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ‘'。
4. 题解
关键在于的理解，有 ‘*’ 存在，可能有很多种情况，不匹配字符？匹配一次字符？匹配两次字符？……但是其根本情况就是两种，即跳过 ‘*’ 及其前边的字符，以及在当前字符匹配的情况下，继续让 ‘*’ 及其前边的字符继续匹配更多字符。想清楚这一点后问题就会变得非常简单
return isMatch(i_str, strIndex, i_pattern, patternIndex + 2)
|| firstLetterMatch && isMatch(i_str, strIndex + 1, i_pattern, patternIndex)
;
class Solution
{
private:
bool isMatch(string &i_str, int strIndex, string &i_pattern, int patternIndex)
{
if(patternIndex == i_pattern.size()) return strIndex == i_str.size();
bool firstLetterMatch = (strIndex < i_str.size()
&& (i_str[strIndex] == i_pattern[patternIndex] || i_pattern[patternIndex] == '.'));
if(patternIndex + 1 < i_pattern.size() && i_pattern[patternIndex + 1] == '*')
{
return isMatch(i_str, strIndex, i_pattern, patternIndex + 2)
|| firstLetterMatch && isMatch(i_str, strIndex + 1, i_pattern, patternIndex)
;
}
else
{
return firstLetterMatch && isMatch(i_str, strIndex + 1, i_pattern, patternIndex + 1);
}
}
public:
// bool isMatch(string s, string p)
bool isMatch(string &i_str, string &i_pattern)
{
return isMatch(i_str, 0, i_pattern, 0);
}
};