数据结构
网络
关系数据库管理系统 (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 次查看
广告