題目
描述
給你一個字串 s 和一個字符規律 p，請你來實作一個支持 '.' 和 '*' 的正則運算式匹配，
'.'匹配任意單個字符'*'匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字串 s的，而不是部分字串，
示例1
輸入：s = "aa" p = "a"
輸出：false
解釋："a" 無法匹配 "aa" 整個字串，示例2
輸入：s = "aa" p = "a*"
輸出：true
解釋：因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'，因此，字串 "aa" 可被視為 'a' 重復了一次，示例3
輸入：s = "ab" p = ".*"
輸出：true
解釋：".*" 表示可匹配零個或多個（'*'）任意字符（'.'），示例4
輸入：s = "aab" p = "c*a*b"
輸出：true
解釋：因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復一次，因此可以匹配字串 "aab"，示例5
輸入：s = "mississippi" p = "mis*is*p*."
輸出：false提示
（1）0 <= s.length <= 20
（2）0 <= p.length <= 30
（3）s 可能為空，且只包含從 a-z 的小寫字母，
（4）p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *，
（5）保證每次出現字符 * 時，前面都匹配到有效的字符
解題思路
（1）使用動態規劃對字串進行匹配
（2）創建（m+1）行（n+1）列的dp矩陣f
（3）以s = "mississippi" p = "mis*is*p*."為例，創建11行11列的dp矩陣f
| "" | m | mi | mis | mis* | mis*i | mis*is | mis*is* | mis*is*p | mis*is*p* | mis*is*p*. | |
| “” | T | F | F | F | F | F | F | F | F | F | F |
| m | F | T | F | F | F | F | F | F | F | F | F |
| mi | F | F | T | F | T | F | F | F | F | F | F |
| mis | F | F | F | T | T | F | F | F | F | F | F |
| miss | F | F | F | F | T | F | F | F | F | F | F |
| missi | F | F | F | F | F | T | F | T | F | F | F |
| missis | F | F | F | F | F | F | T | T | F | T | F |
| mississ | F | F | F | F | F | F | F | T | F | T | T |
| mississi | F | F | F | F | F | F | F | F | F | T | T |
| mississip | F | F | F | F | F | F | F | F | F | F | T |
| mississipp | F | F | F | F | F | F | F | F | F | F | F |
| mississippi | F | F | F | F | F | F | F | F | F | F | F |
（4）如果最新字符為“.”，用match函式來匹配前一個字符，如果行列的兩個字符相等，那只需要考慮沒有增加新的字符時的結果，相等的話，那新增之后也相等
if matches(i, j):
f[i][j] = f[i - 1][j - 1]
def matches(i: int, j: int) -> bool:
if p[j - 1] == '.':
return True
（5）如果新增字符為“*”，則考慮“*”的四種狀態，0個，1個，2個，多個字符（多個不考慮，因為多個是由多個2個組成，可以在i+1中體現）
（6）0個前面字符時相當與洗掉了兩個字符，前面字符和“*”
例子：mis*與miss對比，如果是0個字符時，則為mi與miss對比
f[i][j] = f[i][j - 2]（7）1個前面字符時用match函式判斷新增字符與前一個字符是否相等
例子：mis*與miss對比，如果是1個字符時，則為mis與miss對比
f[i][j] = f[i - 1][j]（7）2個前面字符時用match函式判斷沒有添加兩個新增字符時是否相等
例子：mis*與miss對比，如果是2個字符時，則為miss與miss對比，match函式判斷mis與mis是否相等
if matches(i, j):
f[i][j] = f[i - 1][j - 1]
def matches(i: int, j: int) -> bool:
return s[i - 1] == p[j - 1]（8）最后輸出f[m][n]
（9）對于動態規劃的一些思考：每次以最新一行為基礎，根據問題背景考慮復用前一行或者多行的最優結果，作為本行的最優進行填充，如果需要考慮到計算，則以考慮本行的最優和不考慮本行的最優擇取最優，
代碼
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
def matches(i: int, j: int) -> bool:
if i == 0:
return False
if p[j - 1] == '.':
return True
return s[i - 1] == p[j - 1]
f = [[False] * (n + 1) for _ in range(m + 1)]
f[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
f[i][j] = f[i][j - 2]
if matches(i, j - 1):
f[i][j] = f[i - 1][j]
else:
if matches(i, j):
f[i][j] = f[i - 1][j - 1]
return f[m][n]Reference
題庫 - 力扣 (LeetCode) 全球極客摯愛的技術成長平臺
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/300792.html
標籤：其他
下一篇：Java 17到底有多快？