剑指Offer(Python多种思路实现):正则表达式匹配
面试19题：
题目：正则表达式匹配
题：请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配。
解题思路一：
class Soultion:
def match(self, s, pattern):
if len(s) == 0 and len(pattern) ==
在编程面试中，正则表达式匹配是一个常见的问题，它要求编写一个函数来判断一个给定的字符串是否能被一个包含特殊字符'.'和'*'的模式所匹配。在这个问题中，'.'代表任何单个字符，而'*'表示其前一个字符可以出现任意次，包括0次。例如，字符串"aaa"可以匹配模式"a.a"和"ab*ac*a"，但不能匹配"aa.a"和"ab*a"。
以下两种不同的Python实现方法来解决这个问题：
**解题思路一：**
这个解决方案采用了递归的方法。检查基本情况，即当字符串和模式都为空时，返回True；若字符串非空但模式为空，则返回False。接下来，处理模式中存在'*'的情况，有两种情况需要考虑：
1. 如果模式的第一个字符和第二个字符是'*'，则有三种匹配可能：忽略'*'和它前面的字符，或者尝试匹配一次或多次前一个字符。
2. 如果模式的第二个字符不是'*'，则检查当前字符是否与模式的第一个字符匹配，如果不匹配则直接返回False，否则继续匹配剩余部分。
代码如下：
```python
class Solution:
def match(self, s, pattern):
if len(s) == 0 and len(pattern) == 0:
return True
if len(s) > 0 and len(pattern) == 0:
return False
# 处理模式中第二个字符为'*'的情况
if len(pattern) > 1 and pattern[1] == "*":
if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s, pattern[2:]) or \
self.match(s[1:], pattern[2:]) or \
self.match(s[1:], pattern)
else:
return self.match(s, pattern[2:])
# 模式中第二个字符不是'*'的情况
if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'):
return self.match(s[1:], pattern[1:])
return False
```
**解题思路二：**
第二种解法同样采用递归，但思路稍有不同。检查模式是否为空，如果为空则比较字符串是否为空。接着，检查模式的第一个字符是否为'*'，如果是，那么有三种可能的匹配情况：忽略'*'及其前一个字符，或尝试匹配前一个字符零次或多次。如果模式的第一个字符不是'*'，则检查当前字符是否与模式的第一个字符匹配，如果不匹配则返回False，否则继续匹配剩余部分。
代码如下：
```python
class Solution:
def match(self, s, pattern):
if not pattern:
return not s
f_match = bool(s) and pattern[0] in {s[0], '.'}
if len(pattern) > 1 and pattern[1] == '*':
return (self.match(s, pattern[2:]) or
(f_match and self.match(s[1:], pattern)))
else:
return f_match and self.match(s[1:], pattern[1:])
```
这两种方法都利用了递归的思想，通过逐步缩小问题规模来求解。在实际面试或编程挑战中，需要注意处理边界情况和优化递归深度，以避免不必要的性能开销。同时，理解正则表达式的逻辑和如何用代码模拟它的行为是解决这类问题的关键。
