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:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

思路

本题的目的是为了实现正则表达式中的'*'与'.'两个符号，其中'*'代表其前一个字符可被重复0到n次，而'.'字符代表单个任意字符。当p（正则表达式）与s（被匹配字符）进入函数之后，我们会判断p是否为空，若为空则判断s是否为空，若均为空则返回True，否则为False。然后我们会判断p是否为最后一个字符，若是则判断s是否匹配并返回相应结果。接下来会判断是否为'*'，这是由于'*'本身不具有属性，所以我们将其与它之前的字符看作为一个字符，特性使然。若不为'*'，则判断p与s首字符是否保持一致，若一致则将s剩余的字符串与p剩余字符串一起放入本函数进行递归，递归全部结束后返回正确结果，若为'*'，由于其不能为首位，首字符必然是具备属性的字符，我们通过其后一个字符[1]是否为*号即可了解是否需要通过while循环来判断s首字符之后的每个字符是否均相同，若相同则s字符串向后移动，若不同则跳出循环，将s剩余的字符串与p剩余字符串一起放入本函数进行递归，递归全部结束后返回正确结果。

class Solution:
    def isMatch(self, s, p):
        if len(p) == 0:
            if len(s) == 0:
                return True
            else:
                return False
        if len(p) == 1:
            #若p剩余一个字符 s也剩余一个字符且相同则true 否则为false
            return len(s) == 1 and (p == "." or p == s)
        # 若p的0字符之后的字符不等于*说明不进行通配
        if p[1] != "*":
            # 此时若s为空则错误
            if len(s) == 0:
                return False
            # 此时若s不为空时判断0字符是否一致 且字符串继续递归判断
            return (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        # 若p的0字符之后的字符等于*进行通配
        # s数量不能为0且s字符与p字符一致开始循环
        while (len(s) != 0 and (s[0] == p[0] or p[0] == ".")):
            # 递归判断后续位数 若成功则true
            if self.isMatch(s, p[2:]):
                return True
            # s字符串向后移动1位
            s = s[1:]

        # 递归判断后续位数 并返回结果
        return self.isMatch(s, p[2:])