題目

（困難）給定一個(gè)字符串 (s) 和一個(gè)字符模式 (p)惧财。實(shí)現(xiàn)支持 '.' 和 '*' 的正則表達(dá)式匹配。

'.' 匹配任意單個(gè)字符扭仁。
'*' 匹配零個(gè)或多個(gè)前面的元素垮衷。
匹配應(yīng)該覆蓋整個(gè)字符串 (s) ，而不是部分字符串乖坠。

說(shuō)明：

s 可能為空搀突，且只包含從 a-z 的小寫字母。
p 可能為空熊泵，且只包含從 a-z 的小寫字母仰迁，以及字符 . 和 *。

示例

示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無(wú)法匹配 "aa" 整個(gè)字符串顽分。

示例 2:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: '*' 代表可匹配零個(gè)或多個(gè)前面的元素, 即可以匹配 'a' 徐许。因此, 重復(fù) 'a' 一次, 字符串可變?yōu)?"aa"。

示例 3:

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個(gè)或多個(gè)('*')任意字符('.')卒蘸。

示例 4:
輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 'c' 可以不被重復(fù), 'a' 可以被重復(fù)一次绊寻。因此可以匹配字符串 "aab"。

示例 5:
輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false

解答

這道題的難度是困難悬秉，但是筆者認(rèn)為非常經(jīng)典澄步，有必要好好研究研究。

這里模板匹配有三個(gè)主要規(guī)則和泌，有些概念需要大家理解：

1. 字符的一一對(duì)應(yīng)村缸；

2. 字符“.”可以代替任何一個(gè)字符，暫且稱之為取代符武氓；

3. 字符“*”可以表示該符號(hào)之前的任何字符可以重復(fù)任意次梯皿，可以是零，為了便于表示县恕，我們暫且把該符號(hào)“*”連同其前方的字符一起成為一個(gè)重復(fù)子东羹，把符號(hào)“*”之前的一個(gè)字符稱作重復(fù)基元素，例如重復(fù)子“a*”的重復(fù)基元素為“a”忠烛，因此属提，每個(gè)重復(fù)子由兩個(gè)字符組成，特殊的，重復(fù)基元素“.*”的重復(fù)子可以代表任意字符重復(fù)任意次冤议，我們稱之為任意重復(fù)子斟薇，這種自由度也就增加了題目的復(fù)雜性。

方案1：回溯法

筆者這里的回溯法參考了大神博客恕酸，但是是用java寫的堪滨，力扣可以通過(guò)，筆者改成了python版本蕊温，表示時(shí)間超出限制袱箱。不過(guò)更加建議下面的方案2，動(dòng)態(tài)規(guī)劃义矛。

class Solution:
    """
    采用回溯法
    """
    def isMatch(self, s, p):    # 主函數(shù)
        def remove_repeated_patterns(p):  # 刪除多于的重復(fù)子犯眠，例如“a*a*a*”簡(jiǎn)化為“a*”
            p_list = []
            i = 0
            while i < len(p):
                cur_char = p[i]
                next_char = p[i+1] if i+1 < len(p) else None
                if next_char == '*':
                    star_pattern = cur_char+next_char
                    i += 2
                    if p_list and (p_list[-1] == star_pattern or p_list[-1] == '.*'):
                        continue
                    else:
                        p_list.append(star_pattern)
                else:
                    p_list.append(cur_char)
                    i += 1
            return ''.join(p_list)

        def is_empty_pattern(p):  # 用于判斷模板p可否匹配空字符串
            if not p:
                return True
            if len(p) % 2 != 0:
                return False
            for idx in range(len(p)):
                if idx % 2 == 0:
                    if p[idx] == '*':
                        return False
                else:
                    if p[idx] != '*':
                        return False
            return True

        def match(s, p):
            if len(p) == 0:
                return len(s) == 0

            if len(s) == 0:
                return is_empty_pattern(p)

            first_match = len(s) > 0 and ((p[0] == s[0]) or (p[0] == '.'))

            if len(p) >= 2 and p[1] == '*':
                # 看有沒有可能, 剩下的pattern匹配上全部的text
                return match(s, p[2:]) or (first_match & match(s[1:], p))
            else:
                return first_match & match(s[1:], p[1:])

        p = remove_repeated_patterns(p)
        return match(s, p)

方案2：動(dòng)態(tài)規(guī)劃（建議）

使用動(dòng)態(tài)規(guī)劃會(huì)使匹配流程簡(jiǎn)潔很多，動(dòng)態(tài)規(guī)劃的思想在于以空間換時(shí)間症革，而實(shí)際上這道題目的空間開銷也不大。

【矩陣定義】

首先鸯旁，我們定義一個(gè)矩陣dp噪矛，行數(shù)為s的長(zhǎng)度，列數(shù)為p的長(zhǎng)度铺罢，矩陣中的每一個(gè)元素都是布爾量艇挨，dp[i][j]表示s[:i+1]和p[:j+1]的匹配結(jié)果。

（給基礎(chǔ)薄弱的同學(xué)補(bǔ)充一下韭赘，python中字符串和列表的下標(biāo)從零開始缩滨，索引左閉右開，s[2:5]表示下標(biāo)為2的元素到下標(biāo)為4的元素一共3個(gè)泉瞻，下標(biāo)5所在的元素不取的脉漏。因此可以把dp[i][j]理解為從1到i位置為止的s子串（含i位置）與從1到j(luò)位為止的p子串（含j位置）的匹配結(jié)果。）

【初始情況】

dp建立初始化為None袖牙，這里需要注意的是侧巨，為了正確表示i=0和j=0的情況，我們?cè)黾恿说谝恍泻偷谝涣斜薮铮⑶矣貌粫?huì)用到的字符“司忱！”和“？”來(lái)填充畴蹭。

1. 當(dāng)i和j均為0坦仍，空字符串和空字符串是匹配的，設(shè)置dp[0][0]=0叨襟；

2. 當(dāng)j為零時(shí)繁扎，也就是模板p為空字符串時(shí)，如果i>0糊闽，即如果s不是空字符串锻离，則一定不匹配铺峭；

3. 當(dāng)i為零時(shí)，即字符串s為空串汽纠，這時(shí)需要保證p為空或p是n個(gè)重復(fù)子的組合才能匹配卫键，這里的n為非負(fù)整數(shù)，例如"a*b*"等虱朵。

【狀態(tài)方程】

如何得到dp[i][j]呢莉炉？我們逐行遍歷擴(kuò)大子串s長(zhǎng)度，其中對(duì)每個(gè)子串[:i+1]碴犬，我們逐列遍歷探究子模板p[:j+1]是否與之匹配絮宁，并及時(shí)將計(jì)算結(jié)果儲(chǔ)存在dp矩陣中。根據(jù)匹配規(guī)則服协，有三種情況要考慮：

1. 如果子模板p[:j+1]中新增的元素p[j]是取代符“.”绍昂，或者p[j]與當(dāng)前子串s[:i+1]中的最后一個(gè)元素s[i]相同，則p[:j+1]與s[:i+1]的匹配與否取決于子模板p[:j]與s[:i]的匹配結(jié)果偿荷，即dp[i][j]=dp[i-1][j-1]窘游；

2. 如果子模板p[:j+1]中新增的元素p[j]是“*”，這時(shí)子模板p[j+1]的末尾兩個(gè)字符就構(gòu)成了重復(fù)子跳纳，考慮兩種情況：

   （1）如果子模板p[j+1]的末尾重復(fù)子為任意重復(fù)子“.*”忍饰，或者重復(fù)基元素為當(dāng)前子串s[:i+1]的最后一個(gè)字符s[i]，只要滿足下列條件中任一一個(gè)條件寺庄，即可使p[:j+1]與s[i+1]匹配：
   ①. 先看看不加“*”時(shí)能不能匹配艾蓝，如果模板子串不加“*”都可以和當(dāng)前子串匹配，那么加“*”后也沒問題斗塘，相當(dāng)于重復(fù)子的重復(fù)次數(shù)是1赢织，數(shù)學(xué)描述：如果當(dāng)前子串s[:i+1]和去掉“*”的子模板p[:j]匹配，則s[:i+1]與p[:j+1]匹配馍盟；
   ②. 查看一下將當(dāng)前子模板末尾的整個(gè)重復(fù)子（“*”以及之前的一個(gè)字符）去掉敌厘，能不能和當(dāng)前子串匹配，如果可以成功匹配朽合，則在子模板中增加重復(fù)子也沒問題俱两，這時(shí)相當(dāng)于重復(fù)子的重復(fù)次數(shù)為0。數(shù)學(xué)描述：如果當(dāng)前子串s[:i+1]和去掉重復(fù)子的子模板p[:j-1]匹配曹步，則s[:i+1]與p[:j+1]匹配宪彩；
   ③. 最后，我們?cè)倏匆幌卤Ａ糇幽０逯械闹貜?fù)子讲婚，去掉當(dāng)前子串中的最后一個(gè)字符c尿孔，如果這種情況下可以匹配，那么補(bǔ)回字符c后，因?yàn)樯弦粚訔l件要求重復(fù)子中的重復(fù)元素不是c就是“.”活合，因此相當(dāng)于該重復(fù)子恰好可以描述子串中的字符c雏婶。數(shù)學(xué)描述：如果子串s[:i]和當(dāng)前子模板p[:j+1]匹配，則s[:i]末尾增加p[:j+1]末尾重復(fù)子的重復(fù)基元素s[i]后白指，s[i+1]留晚，p[j+1]也一定可以匹配。

   （2）如果子模板p[j+1]的末尾重復(fù)子的重復(fù)基元素不是當(dāng)前子串s[:i+1]的最后一個(gè)字符s[i]告嘲，這時(shí)只能考慮讓改重復(fù)子的重復(fù)次數(shù)為零了错维，也就是說(shuō)，要求去掉重復(fù)子后的子模板和當(dāng)前子串匹配橄唬。數(shù)學(xué)描述：如果當(dāng)前子串s[i+1]和p[j-1]匹配赋焕，則當(dāng)前子串s[i+1]與p[j-1]增加重復(fù)子后的子模板p[j+1]匹配。

   （3）其他情況仰楚，s[i+1]與p[j+1]無(wú)法匹配隆判，即直接設(shè)置dp[i][j]=False。

最后取s[:len(s)]和p[:len(p)]的匹配結(jié)果即dp矩陣最右下角的數(shù)值dp[-1][-1]返回即可僧界。

這里舉個(gè)栗子侨嘀，輸入s="aab"，p="c*a*."捎泻，得到的dp矩陣是這樣：

         !      c     c*    c*a   c*a*  c*a*.
?     True  False   True  False   True  False
a    False  False  False   True   True   True
aa   False  False  False  False   True   True
aab  False  False  False  False  False   True

如果對(duì)dp表格每一步的變遷過(guò)程感興趣，讀者可以安裝pandas擴(kuò)展包埋哟，消除代碼中的部分注釋運(yùn)行查看笆豁。

class Solution:
    def isMatch(self, s: str, p: str):

        # 打印當(dāng)前dp表格，方便大家查看赤赊。

        # def print_dp(s, p, array):
        #     import pandas as pd
        #     df = pd.DataFrame(array, list(s), list(p))
        #     print(df)

        s = "?" + s     # 添加字符闯狱，防止越界
        p = "!" + p

        dp = [[None for _ in range(len(p))] for _ in range(len(s))]     # 構(gòu)造dp矩陣
        dp[0][0] = True                             # s和p均為空串，則匹配

        for i in range(1, len(s)):                  # p為空抛计，s不為空則無(wú)法匹配哄孤，設(shè)置第一列為False
            dp[i][0] = False

        # 當(dāng)s是空串時(shí)，怎樣才能使p和s匹配吹截？
        for j in range(1, len(p)):
            if p[j] == "*" and dp[0][j - 2]:        # s為空瘦陈，p若不為空，則必須為“字符+*”的組合才可匹配
                dp[0][j] = True
            else:
                dp[0][j] = False

        # print_dp(s, p, dp)                        # 打印初始情況下的dp表

        for i in range(1, len(s)):
            for j in range(1, len(p)):

                if p[j] == "." or p[j] == s[i]:     # 如果p中新增的字符可以匹配s中新增的字符
                    dp[i][j] = dp[i - 1][j - 1]     # 當(dāng)前匹配與否取決于s和p中添加字符前的情況

                elif p[j] == "*":                   # 如果遇到“*”
                    if p[j - 1] == s[i] or p[j - 1] == ".":
                        dp[i][j] = (dp[i][j - 1] or dp[i][j - 2] or dp[i - 1][j])
                    elif p[j - 1] != s[i]:          # 重復(fù)字符的次數(shù)只能是1波俄，則觀察有該模板之前的情況
                        dp[i][j] = dp[i][j - 2]

                else:
                    dp[i][j] = False

                # print('\n當(dāng)前字符串s: "{}"晨逝， 模板p: "{}"'.format(s[1:i+1], p[1:j+1]))
                # print_dp(s, p, dp)

        return dp[-1][-1]

執(zhí)行用時(shí) : 80 ms, 在Regular Expression Matching的Python3提交中擊敗了86.67% 的用戶
內(nèi)存消耗 : 12.9 MB, 在Regular Expression Matching的Python3提交中擊敗了98.66% 的用戶

如有疑問或建議，歡迎評(píng)論區(qū)留言~