剑指offer笔记@正则表达式匹配（附Python代码）

本是古典何须时尚 2024-04-18 17:04 25阅读 0赞

## 题目： ##

**请实现一个函数用来匹配包括'.'和'\*'的正则表达式。**

模式中的字符'.'表示任意一个字符，而'\*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab\*ac\*a"匹配，但是与"aa.a"和"ab\*a"均不匹配。

解题思路：

1. 考虑特殊情况：

1.  两个字符串都为空，这时返回true。
2.  第一个字符串s不空，而第二个字符串pattern为空，返回false。
3.  第一个字符串s为空，而第二个字符串pattern非空，则分情况讨论，因为还是有可能匹配成功的（比如第二个字符串是“a\*a\*a\*a\*”，由于‘\*’之前的元素可以出现0次，所以有可能匹配成功）。

2.开始匹配第一个字符。

1.  匹配成功，继续匹配下一个字符。
2.  匹配失败，此时分情况讨论。

*  pattern的下一个字符不为‘\*’：这种情况比较简单，直接匹配当前字符。如果匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的  “匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的当前字符为‘.’,同时str的当前字符不为‘\\0’。
 *  pattern下一个字符为‘\*’时，稍微复杂一些，因为‘\*’可以代表0个或多个。这里把这些情况都考虑到：

1.  当‘\*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘\*’符号；
2.  当‘\*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。（这里匹配1个或多个可以看成一种情况，因为当匹配一个时，由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）

class Solution:
        # s, pattern都是字符串
        def match(self, s, pattern):
            # 如果s与pattern都为空，则True
            if len(s) == 0 and len(pattern) == 0:
                return True
            # 如果s不为空，而pattern为空，则False
            elif len(s) != 0 and len(pattern) == 0:
                return False
            # 如果s为空，而pattern不为空，则需要判断
            elif len(s) == 0 and len(pattern) != 0:
                # pattern中的第二个字符为*，则pattern后移两位继续比较
                if len(pattern) > 1 and pattern[1] == '*':
                    return self.match(s, pattern[2:])
                else:
                    return False
            # s与pattern都不为空的情况
            else:
                # pattern的第二个字符为*的情况
                if len(pattern) > 1 and pattern[1] == '*':
                    # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
                    if s[0] != pattern[0] and pattern[0] != '.':
                        return self.match(s, pattern[2:])
                    else:
                        # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
                        # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
                        # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
                        # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
                        return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
                # pattern第二个字符不为*的情况
                else:
                    if s[0] == pattern[0] or pattern[0] == '.':
                        return self.match(s[1:], pattern[1:])
                    else:
                        return False