資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python中的正則表示式匹配
假設我們有一個輸入字串 s 和另一個輸入字串 p。其中 s 是主字串，p 是模式。我們需要定義一個方法，可以匹配字串中的模式。所以我們需要為支援“.”和“*”的正則表示式實現這一點。
點“.”匹配任何單個字元
星號“*”匹配前面元素的零個或多個。
例如，如果輸入類似於 s = “aa” 和 p = “a.”，則結果為真；對於相同的輸入字串，如果模式是“.*”，則結果也為真。
為了解決這個問題，我們將遵循以下步驟：
ss := s 的大小，ps := p 的大小
建立一個大小為 ss x ps 的 dp 矩陣，並使用 false 值填充它
透過在這些之前新增一個空格來更新 p 和 s
對於 i 的範圍從 2 到 ps
當 p[i] 為星號時，dp[0, i] := dp[0, i - 2]，否則為 False
對於 i 的範圍從 1 到 ss
對於 j 的範圍從 1 到 ps
如果 s[i] 等於 p[j]，或者 p[j] 為點，則
dp[i, j] := dp[i – 1, j – 1]
否則，當 p[j] 為星號時，則
dp[i, j] := dp[i, j - 2]
如果 s[i] 等於 p[j – 1] 或 p[j – 1] 為點，則
dp[i, j] := dp[i, j] 和 dp[i – 1, j] 的最大值
返回 dp[ss, ps]
示例
讓我們看看以下實現以獲得更好的理解：
class Solution(object):
def isMatch(self, s, p):
ss = len(s)
ps = len(p)
dp = [[False for i in range(ps+1)] for j in range(ss+1)]
p = " "+p
s = " " + s
dp[0][0]=True
for i in range(2,ps+1):
dp[0][i] = dp[0][i-2] if p[i]=='*'else False
for i in range(1,ss+1):
for j in range(1,ps+1):
if s[i] ==p[j] or p[j]=='.':
dp[i][j]= dp[i-1][j-1]
elif p[j] == '*':
dp[i][j] = dp[i][j-2]
if s[i] == p[j-1] or p[j-1]=='.':
dp[i][j] = max(dp[i][j],dp[i-1][j])
return dp[ss][ps]
ob = Solution()
print(ob.isMatch("aa", "a."))
print(ob.isMatch("aaaaaa", "a*"))輸入
"aa", "a." "aaaaaa", "a*"
輸出
True True
更新於: 2020年5月26日
423 次檢視
廣告