資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式檢查正則表示式模式是否與字串匹配
假設我們有一個字串s和一個正則表示式模式。我們必須檢查給定的模式是否與給定的字串匹配。在正則表示式中，有一些規則：
.(句點) 匹配任何單個字元
*(星號) 匹配前面元素的零個或多個。
因此，如果輸入類似於 pattern = "h.l*o" s = "hello"，則輸出為 True，因為我們有ra，然後是一個字元
為了解決這個問題，我們將遵循以下步驟：
n := s 的大小
m := p 的大小
定義一個函式 dp()。這將採用 i, j
如果 j 等於 m，則
返回 i 等於 n
當 (i < n 且 (s[i] 等於 p[j] 或 p[j] 等於 ".") 否則為 false 時，match := true
如果 j + 1 & m 且 p[j + 1] 等於 "*"，則
當 dp(i, j + 2) 或 (match 且 dp(i + 1, j)) 時返回 true，否則返回 false
返回 match 且 dp(i + 1, j + 1)
從主方法返回 dp(0, 0)
示例
讓我們看看下面的實現來更好地理解：
class Solution: def solve(self, p, s): n = len(s) m = len(p) def dp(i, j): if j == m: return i == n match = i < n and (s[i] == p[j] or p[j] == ".") if j + 1 < m and p[j + 1] == "*": return dp(i, j + 2) or (match and dp(i + 1, j)) return match and dp(i + 1, j + 1) return dp(0, 0) ob = Solution() pattern = "h.l*o" s = "hello" print(ob.solve(pattern, s))
輸入
"h.l*o", "hello"
輸出
True
更新於：2020年12月22日
477 次檢視
廣告