题目地址：Regular Expression Matching
题目简介：
给定一个字符串(s)和一个字符模式(p)，实现支持'.'和'*'的正则表达式匹配。
- '.'匹配任意单个字符
- '*'匹配零个或多个前面的元素
-
s可以为空，但是字符范围为a-z. -
p可以为空 ，但是字符范围为a-z和.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 precedeng 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
题目解析：
有点类似BFS，尽可能的走到头，都是递归。为了方便设定条件，将问题分解为以下几种情况：
- p的长度为0：即p=""，只有s == ""时返回True;
- p的长度为1：那么只有s 的长度为1，且s= p或者p = "."时，返回True
- p的长度大于1：
- 若p的第二个字符不为“*”，那么说明还得继续向右走。假设此时s的长度为0，则返回False；
- 只要s的长度大于0，且s[0] = p[0]或者p[0] = '.'时，就可以继续向右移动。如果不满足，则返回False；
- 只要s的长度大于0，且s[0] = p[0]或者p[0] = '.'时。但是如果p的第二个字符为"*"时，需要考虑是否跳过这个“*”。因为“s*”代表
个s，假设“s*”用来表示多个‘s’且当前不是最后一个's'，不需要跳过；如果是最后一个's'，那么需要跳过。
- 如果p的第二个字符为‘*’，第一个字符却与s的第一个字符不匹配，那么这里可以直接跳过p的前两个字符。
Python代码：（这里同样试了C++的两种方法，时间和空间差不多，在代码中已经注释）
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if (len(p) == 0):
return len(s) == 0
if (len(p) == 1) :
return (len(s) == 1 and (s == p or p == "."))
if (p[1] != '*') :
if (len(s) == 0):
return False;
return (s[0] == p[0] or p[0] == '.') and self.isMatch(s[1:len(s)], p[1:len(p)]);
if (len(s) and (s[0] == p[0] or p[0] == '.')):
#if (self.isMatch(s, p[2:len(p)])):
# return True;
#s = s[1:len(s)];
return (self.isMatch(s, p[2:len(p)]) or self.isMatch(s[1:len(s)], p))
return self.isMatch(s, p[2:len(p)]);
C++代码1：（这个代码时间效率较为复杂）
class Solution {
public:
bool isMatch(string s, string p) {
if(p.length() == 0)
{
return (s.length() == 0);
}
else if (p.length() == 1)
{
return (s.length() == 1 && (s == p || p == "."));
}
if (p[1] != '*')
{
if (s.length() == 0)
{
return false;
}
return ((s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)));
}
if (s.length() && (p[0] == s[0] || p[0] == '.'))
{
return (isMatch(s,p.substr(2)) || isMatch(s.substr(1),p));
}
return isMatch(s, p.substr(2));
}
};
C++代码2：快速一点
class Solution {
public:
bool isMatch(string s, string p) {
if(p.length() == 0)
{
return (s.length() == 0);
}
else if (p.length() == 1)
{
return (s.length() == 1 && (s == p || p == "."));
}
if (p[1] != '*')
{
if (s.length() == 0)
{
return false;
}
return ((s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)));
}
while (s.length() && (p[0] == s[0] || p[0] == '.'))
{
if(isMatch(s, p.substr(2))) //这里考虑".*"对应空字符串的情况
return true;
s = s.substr(1); //这里对应s[0] = p[0],".*"对应p[0]的情况
//return (isMatch(s,p.substr(2)) || isMatch(s.substr(1),p));
}
return isMatch(s, p.substr(2));
}
};
假如不管时间的话，还可以将代码进行简化如下（但是这个代码可以很好的说明这个题的思路）：
class Solution {
public:
bool isMatch(string s, string p) {
if(p.length() == 0)
{
return (s.length() == 0);
}
if(p.length() > 1 && p[1] == '*')
{
return ((isMatch(s, p.substr(2))) || ((p[0] == s[0] || p[0] == '.') && isMatch(s.substr(1), p)));
}
else
{
return (s.length() != 0 && (p[0] == s[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1)));
}
}
};