class Solution:
def isMatch(self, s: str, p: str) -> bool:
# 判空（結(jié)束）
if not s and not p:
return True
elif s and not p:
return False
# s 第一列表示 s 的 ^
dp = [[False] * (len(s) + 1) for i in range(len(p))]
# 處理第一列
if len(p) > 1:
dp[1][0] = p[1] == '*'
for y in range(2, len(p)):
if not dp[y - 1][0] and not dp[y - 2][0]:
break
dp[y][0] = p[y] == '*'
# 處理第一行剩下的部分
if s:
dp[0][1] = p[0] == s[0] or p[0] == '.'
for y in range(1, len(p)):
for x in range(1, len(s) + 1):
# 先橫再豎
if p[y] == '*':
# 上方為 T 或上上為 T 必為 T酒繁，上為 T 表示這里 * 代表 1奕翔，上為 F 上上為 T 表示這里 * 為 0
if dp[y - 1][x] or dp[y - 2][x]:
dp[y][x] = True
# 其余情況首先左為 T季研，然后看看上一個 p 是不是能匹配當(dāng)前的 s挟憔，左為 T 說明這里的 * 為 > 2磕仅，要檢測能否繼續(xù)匹配
elif dp[y][x - 1] and (p[y - 1] == '.' or p[y - 1] == s[x - 1]):
dp[y][x] = True
elif p[y] == '.':
# 如果左上是 T 那么這里必為 T，s 和 p 都向后移動匹配下一個字符浊洞，反過來需要前面的能匹配上
if dp[y - 1][x - 1]:
dp[y][x] = True
else:
# 普通字符的時候如果左上方已經(jīng)為 F 則必為 F把曼，同 .，s 和 p 都向后移動匹配下一個字符摄乒，反過來需要前面的能匹配上
if dp[y - 1][x - 1] and p[y] == s[x - 1]:
dp[y][x] = True
return dp[-1][-1]
10.正則表達式匹配
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門旦委，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人雏亚，你說我怎么就攤上這事缨硝。” “怎么了罢低？”我有些...
- 文/不壞的土叔 我叫張陵查辩，是天一觀的道長。 經(jīng)常有香客問我，道長宜岛，這世上最難降的妖魔是什么长踊？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮萍倡，結(jié)果婚禮上身弊，老公的妹妹穿的比我還像新娘。我一直安慰自己遣铝，他們只是感情好佑刷，可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著酿炸，像睡著了一般。 火紅的嫁衣襯著肌膚如雪涨冀。 梳的紋絲不亂的頭發(fā)上填硕，一...
- 文/蒼蘭香墨 我猛地睜開眼涝滴，長吁一口氣：“原來是場噩夢啊……” “哼绣版！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起歼疮，我...
- 正文 年R本政府宣布，位于F島的核電站，受9級特大地震影響唁桩，放射性物質(zhì)發(fā)生泄漏闭树。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一荒澡、第九天 我趴在偏房一處隱蔽的房頂上張望报辱。 院中可真熱鬧，春花似錦单山、人聲如沸碍现。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽昼接。三九已至，卻和暖如春悴晰，著一層夾襖步出監(jiān)牢的瞬間慢睡，已是汗流浹背。 一陣腳步聲響...
