題目
（困難）給定一個(gè)字符串 (s) 和一個(gè)字符模式 (p)。實(shí)現(xiàn)支持 '.' 和 '*' 的正則表達(dá)式匹配。
'.' 匹配任意單個(gè)字符。
'*' 匹配零個(gè)或多個(gè)前面的元素。
匹配應(yīng)該覆蓋整個(gè)字符串 (s) ，而不是部分字符串。
說明：
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。
示例
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "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ī)則，有些概念需要大家理解：
字符的一一對應(yīng)；
字符“.”可以代替任何一個(gè)字符，暫且稱之為取代符；
字符“*”可以表示該符號之前的任何字符可以重復(fù)任意次，可以是零，為了便于表示，我們暫且把該符號“*”連同其前方的字符一起成為一個(gè)重復(fù)子，把符號“*”之前的一個(gè)字符稱作重復(fù)基元素，例如重復(fù)子“a*”的重復(fù)基元素為“a”，因此，每個(gè)重復(fù)子由兩個(gè)字符組成，特殊的，重復(fù)基元素“.*”的重復(fù)子可以代表任意字符重復(fù)任意次，我們稱之為任意重復(fù)子，這種自由度也就增加了題目的復(fù)雜性。
方案1：回溯法
筆者這里的回溯法參考了大神博客，但是是用java寫的，力扣可以通過，筆者改成了python版本，表示時(shí)間超出限制。不過更加建議下面的方案2，動(dòng)態(tài)規(guī)劃。
class Solution:
"""
采用回溯法
"""
def isMatch(self, s, p): # 主函數(shù)
def remove_repeated_patterns(p): # 刪除多于的重復(fù)子，例如“a*a*a*”簡化為“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ì)使匹配流程簡潔很多，動(dòng)態(tài)規(guī)劃的思想在于以空間換時(shí)間，而實(shí)際上這道題目的空間開銷也不大。
【矩陣定義】
首先，我們定義一個(gè)矩陣dp，行數(shù)為s的長度，列數(shù)為p的長度，矩陣中的每一個(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的情況，我們增加了第一行和第一列，并且用不會(huì)用到的字符“！”和“？”來填充。
當(dāng)i和j均為0，空字符串和空字符串是匹配的，設(shè)置dp[0][0]=0；
當(dāng)j為零時(shí)，也就是模板p為空字符串時(shí)，如果i>0，即如果s不是空字符串，則一定不匹配；
當(dāng)i為零時(shí)，即字符串s為空串，這時(shí)需要保證p為空或p是n個(gè)重復(fù)子的組合才能匹配，這里的n為非負(fù)整數(shù)，例如"a*b*"等。
【狀態(tài)方程】
如何得到dp[i][j]呢？我們逐行遍歷擴(kuò)大子串s長度，其中對每個(gè)子串[:i+1]，我們逐列遍歷探究子模板p[:j+1]是否與之匹配，并及時(shí)將計(jì)算結(jié)果儲(chǔ)存在dp矩陣中。根據(jù)匹配規(guī)則，有三種情況要考慮：
如果子模板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]；
-
如果子模板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]匹配；
③. 最后，我們再看一下保留子模板中的重復(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ù)為零了，也就是說，要求去掉重復(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]無法匹配，即直接設(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
如果對dp表格每一步的變遷過程感興趣，讀者可以安裝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不為空則無法匹配，設(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% 的用戶
如有疑問或建議，歡迎評論區(qū)留言~
