1.題目

原題

給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配。所謂匹配，是要涵蓋 整個(gè) 字符串 s的，而不是部分字符串。
說(shuō)明:
s 可能為空，且只包含從 a-z 的小寫(xiě)字母。
p 可能為空，且只包含從 a-z 的小寫(xiě)字母，以及字符 . 和 *。

例子

1.輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無(wú)法匹配 "aa" 整個(gè)字符串。
2.輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因?yàn)?'*' 表示零個(gè)或多個(gè)，這里 'c' 為 0 個(gè), 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"。

2.解析

這道題是一道正則題，要求的是完全匹配而非部分匹配，思路有三種。

• python正則包
  python的優(yōu)勢(shì)在于有各種包可以直接調(diào)用，語(yǔ)句比較優(yōu)雅，我們可以直接調(diào)用re包。
  這里邊的知識(shí)點(diǎn)是re.findall和re.match這兩個(gè)函數(shù)的用法。
  其中，findall是找到所有匹配，第一個(gè)匹配是滿足條件的最常字符串，如果不加開(kāi)始和結(jié)束符號(hào)的話，只要有局部匹配，就會(huì)輸出全局字符串。match也一樣只不過(guò)會(huì)按group輸出，此為正則表達(dá)式的知識(shí)，有很多細(xì)節(jié)需要注意。
• 遞歸求解
  題意說(shuō)的是，字符串和正則要完全匹配才能輸出最終的結(jié)果，基本的思路應(yīng)該是一個(gè)一個(gè)字符串去判斷是否是匹配，如果沒(méi)有特殊符號(hào)，這道問(wèn)題就非常簡(jiǎn)單了，現(xiàn)在定義了兩個(gè)特殊字符，主要要實(shí)現(xiàn)他們的功能。
  .匹配任意字符，當(dāng)做一個(gè)判斷條件，就是任意字符串都可以和.相同，只要正則字符串中出現(xiàn).邏輯語(yǔ)句就返回True。
  匹配前面字符0次或多次，難點(diǎn)在于可以不匹配。需要分情況討論，將放在正則字符串的第二個(gè)位置，如果匹配到了號(hào)，則分情況討論，因?yàn)?/em>可以不匹配，那么會(huì)產(chǎn)生很多種情況。
  整體思路可以這么來(lái)理解：
  1）遞歸的程序出口是待匹配字符串p和正則表達(dá)式s，有一個(gè)為空。
  定義一個(gè)出口：如果p為空，則s必須為空，才能返回True，否則返回False。
  2）遞歸每次都需要做判斷，實(shí)際就是逐個(gè)字符的比較，即待匹配字符串p和正則表達(dá)式s，第一個(gè)字符串是否相同，如果相同則繼續(xù)遞歸判斷，這個(gè)需要定義一個(gè)頭部字符串是否相同的變量。
  len(p) > 1 and s[0] == p[0] or p[0] == '.'
  3)這一步是最重要的，分情況來(lái)說(shuō)：
  判斷條件是第二個(gè)字符串是否是*
  如果是：
  判斷第一個(gè)字符串是不是相同，如果相同則匹配成功，將p右移一位和s繼續(xù)匹配；如果第一個(gè)字符串不同，但是*可以不匹配，所以將p和右移兩位的s繼續(xù)匹配。
  如果不是：
  判斷第一個(gè)字符串是不是相同，如果是則將p和s各右移一位進(jìn)行遞歸，如果不是返回false了。
  這里有一個(gè)額外的知識(shí)點(diǎn)就是python and 和 or的執(zhí)行順序問(wèn)題，可以這么理解，如果有括號(hào)是括號(hào)里的先執(zhí)行，如果不是則按照順序執(zhí)行，and的邏輯是如果左邊是False，跳過(guò)右邊，or的邏輯是如果昨天是True，跳過(guò)左邊。
• 動(dòng)態(tài)規(guī)劃求解
  動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的分支，涉及到運(yùn)籌學(xué)了，動(dòng)態(tài)規(guī)劃解決的是最優(yōu)化的問(wèn)題，核心思想就是把大問(wèn)題拆解為小問(wèn)題，可以用動(dòng)態(tài)規(guī)劃求解問(wèn)題的最大特點(diǎn)是：最優(yōu)子結(jié)構(gòu)以及重疊子問(wèn)題兩個(gè)特點(diǎn)，最優(yōu)子結(jié)構(gòu)是保證問(wèn)題可以拆解的，重疊子問(wèn)題是為了防止遞歸重復(fù)計(jì)算的。
  動(dòng)態(tài)規(guī)劃是值得學(xué)習(xí)的一個(gè)方法，筆者正在學(xué)習(xí)中，這里簡(jiǎn)單說(shuō)一下自己的理解，如果有不對(duì)的地方請(qǐng)大家批評(píng)指正。
  動(dòng)態(tài)規(guī)劃最核心的部分是建立一個(gè)矩陣，存儲(chǔ)之前計(jì)算的結(jié)果，防止重復(fù)計(jì)算。
  放到這個(gè)問(wèn)題，前i個(gè)字符串是否匹配是沒(méi)必要重復(fù)計(jì)算的，所以需要建立一個(gè)矩陣dp來(lái)存放。
  定義狀態(tài)函數(shù)f(i,j)，表示字符串p的前i個(gè)字符和正則表達(dá)式s的前j個(gè)字符是否匹配，這里要尤其注意，是前面所有字符，而不是第i個(gè)字符和第j個(gè)字符。
  然后需要考慮幾種不同的情景，第一個(gè)要考慮就是空字符串的匹配問(wèn)題，就是說(shuō)字符串p是空的時(shí)候，什么樣的正則可以和他匹配上。我們這么思考，只有或者空才能匹配空字符串。如果定義dp[0,0] = 0那么空字符串都可以匹配上。然后考慮不會(huì)單獨(dú)出現(xiàn)，會(huì)和一個(gè)字符一起出現(xiàn)，比如a或者ab，所以從正則字符串的第2個(gè)開(kāi)始遍歷（j=2:end），如果是則可以不匹配之前的字符串，跟它之前再之前的一個(gè)（j-2）狀態(tài)相同，這個(gè)相對(duì)比較好理解，因?yàn)橹簧婕耙粚友h(huán)。
  接下來(lái)的比較復(fù)雜，需要考慮非空字符串的匹配問(wèn)題。這里還是從最簡(jiǎn)單的情況入手：
• s[i-1]和p[j-1]相同或者s[i-1]為'.'（可以匹配任意字符）
  這種情況很簡(jiǎn)單，當(dāng)前匹配與否和上一個(gè)狀態(tài)完全一致。即：dp[i][j] = dp[i-1][j-1]
• s[i-1]== ''
  這種情況比較復(fù)雜，有可能s[i-2]匹配0次，匹配1次，匹配很多次。
  1)匹配0次，直接跳過(guò)前一個(gè)字符，結(jié)果和前前字符相同（注意說(shuō)的是哪兩個(gè)字符串相同），即dp[i][j] = dp[i]j-2
  2)匹配1次，前一個(gè)字符是匹配得上的，結(jié)果和前字符相同，即dp[i][j]=dp[i][j-1]
  3)匹配多次，這個(gè)情況比較復(fù)雜，如何滿足匹配多次的條件呢，需要：p(i-1)和s(j-2)相同，或者s(j-2)是’.’，結(jié)果應(yīng)該和p到上一個(gè)字符串位置和s當(dāng)前字符串匹配結(jié)果是相同的，因?yàn)榈?/em>的位置需要匹配多次，所以滿足這個(gè)規(guī)律。

import re
class Solution():
    def isMatch(self, p, s):
        return re.match('^'+s+'$', p) is not None

class Solution():
    def isMatch(self, p, s):
        #最簡(jiǎn)單的情況，s為空
        if not s:
            return not p
        firstmatch = bool(p) and (s[0] == '.' or s[0] == p[0])
        if len(s) > 1 and s[1] == '*':
            return (self.isMatch(p, s[2:]) or
                    firstmatch and self.isMatch(p[1:], s))
        else:
            return firstmatch and self.isMatch(p[1:], s[1:])

class Solution():
    def isMatch(self, p, s):
        dp = [[False for _ in range(len(s) + 1)] for _ in range(len(p) + 1)]
        dp[0][0] = True
        for j in range(2, len(s) + 1):
            if s[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        for i in range(1, len(p) + 1):
            for j in range(1, len(s) + 1):
                if s[j - 1] == p[i-1] or s[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                if s[j - 1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i][j-2] or dp[i-1][j] and (s[j - 2] == '.' or s[j - 2] == p[i - 1])
        return dp[len(p)][len(s)]