1 | Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'. |
题目要求实现一个只支持* 和 . 的正则表达式判定函数
解题思路: 建立一个NFA 然后直接模拟
- 对于非*字符,建立一个新的状态 连一条边
- 对于字符,连一条到自己的边 (字符为之前的那一个字符)
- 重要 由于*可以匹配 0个字符, 需要连一条【之前状态】 到 【现在状态】 【不消耗字符】的边。
- 然后记录下当前状态 暴力转移即可,复杂度最坏O(n*m)
非常挫的实现(大佬勿喷) (56 ms):
1 | class State: |
思路2:DP 比较简单 参考youtube视频
dp[i][j] 表示s[:i] 和 p[:j] 是否匹配
- dp[0][0] = 0
- dp[i][j] = dp[i-1][j-1] if s[i] == p[j] or p[j] ==’.’ 单字符匹配
- dp[i][j] = dp[i][j-2] if p[j]==’*’ 星号部分完全省略
- dp[i][j] = dp[i-1][j] if p[j]==’*’ and s[i] == p[j-1] 星号部分重复至少一次
- 答案是dp[n][m]
1 | class Solution: |
Bonus
LeetCode 44. Wildcard Matching
用同样的思路可以直接秒掉更简单版本的44题
1 | Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. |
1 | class Solution: |