正則表達(dá)式匹配

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

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

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

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

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

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

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í)行用時(shí)：1100 ms，執(zhí)行效率算很差，只超過(guò)了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í)行用時(shí)間優(yōu)化到140 ms，但也只超過(guò)了40%的提交效率。
不過(guò)查別人效率比我高的提交中，很多人用的是re庫(kù)中的匹配函數(shù)，心里略微平衡了一點(diǎn)

把別人提交的效率最高的代碼貼出來(lái)：

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

GPU云服務(wù)器云服務(wù)器正則匹配正則表達(dá)式正則表達(dá)式匹配匹配php正則表達(dá)式 js正則表達(dá)匹配

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/42748.html

相關(guān)文章

JavaScript正則表達(dá)式的匹配模式

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

wqj97 2019-08-20 18:56 評(píng)論0 收藏0
JS正則表達(dá)式一條龍講解，從原理和語(yǔ)法到JS正則、ES6正則擴(kuò)展，最后再到正則實(shí)踐思路

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

Michael_Lin 2019-08-20 13:39 評(píng)論0 收藏0
JavaScript正則表達(dá)式總結(jié)

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

big_cat 2019-08-22 18:32 評(píng)論0 收藏0
JavaScript 中的正則表達(dá)式

摘要：正則表達(dá)式的意義中的正則表達(dá)式使用表示，可以使用構(gòu)造函數(shù)來(lái)創(chuàng)建對(duì)象，不過(guò)對(duì)象更多的是通過(guò)一種特殊的直接量語(yǔ)法來(lái)創(chuàng)建。用構(gòu)造函數(shù)也可以定義一個(gè)與之等價(jià)的正則表達(dá)式，代碼如下正則表達(dá)式的模式規(guī)則是由一個(gè)字符序列組成的。正則表達(dá)式的模式匹配正則表達(dá)式(regular expression)是一個(gè)描述字符模式的對(duì)象。javascript的RegExp對(duì)象表示正則表達(dá)式，String和Reg...

_Dreams 2019-08-19 18:40 評(píng)論0 收藏0
JavaScript正則表達(dá)式

摘要：引用就是允許在同一個(gè)正則表達(dá)式的后部引用前面的子表達(dá)式。這個(gè)數(shù)字制定了帶圓括號(hào)的子表達(dá)式在正則表達(dá)式中的位置。對(duì)正則表達(dá)式中前一個(gè)子表達(dá)式的引用，并不是指對(duì)子表達(dá)式模式的引用，而是指與那個(gè)模式匹配的文本的引用。前言本文主要是在讀《JavaScript高級(jí)程序語(yǔ)言設(shè)計(jì)》一書(shū)有關(guān)正則表達(dá)式的章節(jié)的知識(shí)點(diǎn)記錄，方便后續(xù)查閱。什么是正則表達(dá)式正則表達(dá)式是用來(lái)描述字符組合的某種規(guī)則。它可...

sixleaves 2019-08-21 11:17 評(píng)論0 收藏0
正則與JS中的正則

摘要：注意本文將正則與中的正則分開(kāi)討論。正則零寬斷言更多參考各種語(yǔ)言對(duì)于正則不同支持參考單行模式與多行模式通過(guò)設(shè)置正則表達(dá)式后的修飾符可開(kāi)啟對(duì)應(yīng)的匹配模式單行模式和多行模式。最近這段時(shí)間幫同學(xué)處理一些文檔，涉及到一些結(jié)構(gòu)化文檔的工作大部分都得使用正則表達(dá)式，之前對(duì)于正則的認(rèn)識(shí)大多來(lái)源于語(yǔ)言書(shū)上那幾頁(yè)的介紹，自己也沒(méi)有用過(guò)幾次。這里將我之前感到模糊的概念作個(gè)整理。因?yàn)閷?duì)JS了解多點(diǎn)，所...

firim 2019-08-19 17:11 評(píng)論0 收藏0