<ul id="eo2oy"></ul><del id="eo2oy"></del>

<fieldset id="eo2oy"></fieldset>

<ul id="eo2oy"></ul>

正則表達(dá)式匹配

Charles 發(fā)布于2019-07-30 18:37 / 2133人閱讀

摘要：實現(xiàn)支持和的正則表達(dá)式匹配。匹配任意單個字符。匹配零個或多個前面的元素。匹配應(yīng)該覆蓋整個字符串，而不是部分字符串。不過查別人效率比我高的提交中，很多人用的是庫中的匹配函數(shù)，心里略微平衡了一點把別人提交的效率最高的代碼貼出來執(zhí)行只用

leetcode上面的題目解題及重構(gòu)
題干：給定一個字符串 (s) 和一個字符模式 (p)。實現(xiàn)支持 "." 和 "*" 的正則表達(dá)式匹配。

 "." 匹配任意單個字符。 
 "*" 匹配零個或多個前面的元素。

匹配應(yīng)該覆蓋整個字符串 (s) ，而不是部分字符串。
說明:
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。
題目及示例傳送門

如果直接用re，那這題就沒意義了，所以肯定要自己寫匹配算法
第一次成功提交代碼：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        if len(p) == 1:
            return len(s) == 1 and (s == p or p == ".")
        if p[1] != "*":
            if s == "":
                return False
            return (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        while s and (p[0] == s[0] or p[0] == "."):
            if self.isMatch(s, p[2:]):
                return True
            s = s[1:]
        return self.isMatch(s, p[2:])

執(zhí)行用時：1100 ms，執(zhí)行效率算很差，只超過了32%的提交效率
優(yōu)化后第二次提交：

def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        if len(p) == 1:
            return False if len(s) != 1 else (s == p or p == "." or p == "*")
        if (p[-1] != "*") and (p[-1] != ".") and (p[-1] not in s): 
            return False 
        if (p[1] != "*"): 
            return s != "" and (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        else:
            while s and (p[0] == s[0] or p[0] == "."):
                if self.isMatch(s, p[2:]):
                    return True
                s = s[1:]
            return self.isMatch(s, p[2:])

執(zhí)行用時間優(yōu)化到140 ms，但也只超過了40%的提交效率。
不過查別人效率比我高的提交中，很多人用的是re庫中的匹配函數(shù)，心里略微平衡了一點

把別人提交的效率最高的代碼貼出來：

class Solution(object):
    def isMatch(self, s, p, memo={("",""):True}):
        if not p and s:      return False
        if not s and p:      return set(p[1::2]) == {"*"} and not (len(p) % 2)
        if (s,p) in memo:    return memo[s,p]

        char, exp, prev = s[-1], p[-1], 0 if len(p) < 2 else p[-2]
        memo[s,p] =
               (exp == "*" and ((prev in {char, "."} and self.isMatch(s[:-1], p, memo)) or self.isMatch(s, p[:-2], memo)))
               or
               (exp in {char, "."} and self.isMatch(s[:-1], p[:-1], memo))
        return memo[s,p]

執(zhí)行只用36ms