正則表達式匹配

Charles 發布于2019-07-30 18:37 / 2125人閱讀

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

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

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

匹配應該覆蓋整個字符串 (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:])

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

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:])

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

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

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]

執行只用36ms

云服務器 GPU云服務器正則匹配正則表達式正則表達式匹配匹配php正則表達式 js正則表達匹配

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/42748.html

JavaScript正則表達式的匹配模式

摘要：選擇分組和引用正則表達式的語法還包括指定選擇項子表達式分組和引用前一子表達式的特殊字符。帶圓括號的表達式的另一個用途是允許在同一正則表達式的后部引用前面的子表達式。正則表達式(regular expression)是一個描述字符模式的對象。JavaScript的 RegExp類表示正則表達式，String和RegExp都定義了方法，后者使用正則表達式進行強大的模式匹配和文本檢索與...

wqj97 2019-08-20 18:56 評論0 收藏0
JS正則表達式一條龍講解，從原理和語法到JS正則、ES6正則擴展，最后再到正則實踐思路

摘要：控制權和傳動這兩個詞可能在搜一些博文或者資料的時候會遇到，這里做一個解釋先控制權是指哪一個正則子表達式可能為一個普通字符元字符或元字符序列組成在匹配字符串，那么控制權就在哪。溫馨提示：文章很長很長，保持耐心，必要時可以跳著看，當然用來查也是不錯的。正則啊，就像一座燈塔，當你在字符串的海洋不知所措的時候，總能給你一點思路；正則啊，就像一臺驗鈔機，在你不知道用戶提交的鈔票真假的時候，...

Michael_Lin 2019-08-20 13:39 評論0 收藏0
JavaScript正則表達式總結

摘要：正則表達式一直是里比較難以掌握的點。在中創建正則的兩種方式使用字面量這就是正則表達式的字面量語法，表示正則表達式的模式，為正則表達式的標志。字面量形式的正則表達式一般使用較多，也推薦大家盡可能使用這種形式，簡潔易讀，符合正常的使用習慣。正則表達式一直是js里比較難以掌握的點。看不懂，學不會，記不住。每次需要用到正則的時候，都需要再去查找資料。今天花時間把正則的知識點總結下，希望...

big_cat 2019-08-22 18:32 評論0 收藏0
JavaScript 中的正則表達式

摘要：正則表達式的意義中的正則表達式使用表示，可以使用構造函數來創建對象，不過對象更多的是通過一種特殊的直接量語法來創建。用構造函數也可以定義一個與之等價的正則表達式，代碼如下正則表達式的模式規則是由一個字符序列組成的。正則表達式的模式匹配正則表達式(regular expression)是一個描述字符模式的對象。javascript的RegExp對象表示正則表達式，String和Reg...

_Dreams 2019-08-19 18:40 評論0 收藏0
JavaScript正則表達式

摘要：引用就是允許在同一個正則表達式的后部引用前面的子表達式。這個數字制定了帶圓括號的子表達式在正則表達式中的位置。對正則表達式中前一個子表達式的引用，并不是指對子表達式模式的引用，而是指與那個模式匹配的文本的引用。前言本文主要是在讀《JavaScript高級程序語言設計》一書有關正則表達式的章節的知識點記錄，方便后續查閱。什么是正則表達式正則表達式是用來描述字符組合的某種規則。它可...

sixleaves 2019-08-21 11:17 評論0 收藏0
正則與JS中的正則

摘要：注意本文將正則與中的正則分開討論。正則零寬斷言更多參考各種語言對于正則不同支持參考單行模式與多行模式通過設置正則表達式后的修飾符可開啟對應的匹配模式單行模式和多行模式。最近這段時間幫同學處理一些文檔，涉及到一些結構化文檔的工作大部分都得使用正則表達式，之前對于正則的認識大多來源于語言書上那幾頁的介紹，自己也沒有用過幾次。這里將我之前感到模糊的概念作個整理。因為對JS了解多點，所...

firim 2019-08-19 17:11 評論0 收藏0