問題描述

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

思路

本題的目的是為了實現(xiàn)正則表達(dá)式中的'*'與'.'兩個符號，其中'*'代表其前一個字符可被重復(fù)0到n次，而'.'字符代表單個任意字符。當(dāng)p（正則表達(dá)式）與s（被匹配字符）進(jìn)入函數(shù)之后，我們會判斷p是否為空，若為空則判斷s是否為空，若均為空則返回True，否則為False。然后我們會判斷p是否為最后一個字符，若是則判斷s是否匹配并返回相應(yīng)結(jié)果。接下來會判斷是否為'*'，這是由于'*'本身不具有屬性，所以我們將其與它之前的字符看作為一個字符，特性使然。若不為'*'，則判斷p與s首字符是否保持一致，若一致則將s剩余的字符串與p剩余字符串一起放入本函數(shù)進(jìn)行遞歸，遞歸全部結(jié)束后返回正確結(jié)果，若為'*'，由于其不能為首位，首字符必然是具備屬性的字符，我們通過其后一個字符[1]是否為*號即可了解是否需要通過while循環(huán)來判斷s首字符之后的每個字符是否均相同，若相同則s字符串向后移動，若不同則跳出循環(huán)，將s剩余的字符串與p剩余字符串一起放入本函數(shù)進(jìn)行遞歸，遞歸全部結(jié)束后返回正確結(jié)果。

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字符之后的字符不等于*說明不進(jìn)行通配
        if p[1] != "*":
            # 此時若s為空則錯誤
            if len(s) == 0:
                return False
            # 此時若s不為空時判斷0字符是否一致 且字符串繼續(xù)遞歸判斷
            return (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        # 若p的0字符之后的字符等于*進(jìn)行通配
        # s數(shù)量不能為0且s字符與p字符一致開始循環(huán)
        while (len(s) != 0 and (s[0] == p[0] or p[0] == ".")):
            # 遞歸判斷后續(xù)位數(shù) 若成功則true
            if self.isMatch(s, p[2:]):
                return True
            # s字符串向后移動1位
            s = s[1:]

        # 遞歸判斷后續(xù)位數(shù) 并返回結(jié)果
        return self.isMatch(s, p[2:])