手動實現(xiàn).*正則表達式匹配函數(shù)

muddyway 發(fā)布于2019-07-25 12:02 / 1038人閱讀

摘要：手動實現(xiàn)正則表達式匹配函數(shù)思路使用迭代，當每次判斷后令當時特殊處理，注意可以代表到多個之前一個的字符當時，循環(huán)判斷代表多少個之前一個的字符，如果可以匹配之后的模式，返回，否則注意處理邊界值的情況，和為空串時代碼可以代表一到多次本題以及其它題

手動實現(xiàn).*正則表達式匹配函數(shù) regular expression matching

"." Matches any single character.

"*" Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("bbbba", ".*a*a") → true
isMatch("a", ".*..a*") → False
isMatch("a", "ab*") → true 
isMatch("ab", ".*c") → False

思路

使用迭代，當p[1] != "*"每次判斷p[0] == s[0]后令s = s[1:], p = p[1:]

當p[1] == "*"時特殊處理，注意 * 可以代表0到多個*之前一個的字符

當p[1] == "*"時，循環(huán)判斷*代表多少個*之前一個的字符，如果s可以匹配*之后的模式，返回True，否則s = s[1:]

注意處理邊界值的情況，s 和 p為空串時

代碼

class Solution(object):
    def matchChar(self, sc, pc):
        return sc == pc or pc == "."

    def isEndOfStar(self, p):
        while p != "":
            if len(p) == 1 or len(p) > 1 and p[1] != "*":
                return False
            p = p[2:]
        return True

    def isMatch(self, s, p):
        if p == "":
            return s == ""

        if s == "":
            return self.isEndOfStar(p)

        if (len(p) > 1 and p[1] != "*") or len(p) == 1:
            # without *
            if not self.matchChar(s[0], p[0]):
                return False
            else:
                return self.isMatch(s[1:], p[1:])

        else:
            # with *
            # try see x* is empty
            if self.isMatch(s[0:], p[2:]):
                return True

            # x* 可以 代表 x 一到多次
            while self.matchChar(s[0], p[0]):
                s = s[1:]

                if self.isMatch(s, p[2:]):
                    return True

                if s == "":
                    return self.isEndOfStar(p)
            return False

本題以及其它leetcode題目代碼github地址: github地址