Leetcode 10 正则表达式匹配问题

|
| 字数统计: 722

Regular Expression Matching

Given an input string (s) and a pattern §, implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

#Note：
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

#Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

#Example 2:

Input:
s = “aa”
p = “a*”
Output: true
Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

#Example 3:

Input:
s = “ab”
p = “.*”
Output: true
Explanation: “." means "zero or more () of any character (.)”.

#Example 4:

Input:
s = “aab”
p = “c*a*b”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

#Example 5:

Input:
s = “mississippi”
p = “mis*is*p*.”
Output: false

正则表达式匹配，想偷懒的话，直接调用python的re库

1
2
3
4
import re
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        return re.fullmatch(p, s) != None

比较正规的方法是用动态规划的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        ls=len(s)
        lp=len(p)
        dp = [[True if not j else not ls for j in range(ls+1)] for i in range(lp+1)]
        s=' '+s
        p=' '+p
        for i in range(1, lp+1):
            ast = p[i] == '*'#注此处i-1代表第i个
            dp[i][0] = ast and dp[i-2][0]
            for j in range(1, ls+1):
                dp[i][j] = ast and dp[i-2][j] or p[i-ast] in ('.', s[j]) and dp[i-1+ast][j-1]
                   
        return dp[lp][ls]

分析一下算法思路
其中递推项dp[i][j]表示p的前i个字符与s中前j个字符组成的表示式是否匹配。dp[0][0]恒为True。
对p和s做1个偏移调整

对于p的前i个和s的前j个字符串
需考虑2种情况
㈠当p[i]=’*‘时，dp[i][j]为真有两种情况：
(1)当dp[i-2][j]为真时，利用p[i]=’*’，可将p[i-1]消去，因此dp[i][j]仍为真，
(2)当dp[i][j-1]为真，且p[i]=’*’，则可知s[j-1]一定和p[i-2]或p[i-1]相等
①当s[j-1]==p[i-2]，若s[j]==p[i-1](p[i-1]等于’.‘也成立)，则可以令p[i]的’*‘为重复1次，正好匹配；
②当s[j-1]==p[i-1]，若s[j]==p[i-1](p[i-1]等于’.‘也成立)，则可以令p[i]的’*'为重复2次，正好匹配

㈡当p[i]!=’*‘时，dp[i][j]为真只有一种情况，dp[i-1][j-1]为真且s[j]==p[i](p[i]等于’.'也成立)。

则可以列出下列递推式

dp[i][j]={dp[i−2][j]  ∣∣  (p[i−1]∈{′.′,s[j]}  &&  dp[i][j−1])p[i]==′∗′p[i]∈{′.′,s[j]}  &&  dp[i−1][j−1]p[i]!=′∗′ dp[i][j]=\begin{cases} dp[i-2][j] \ \ ||\ \ (p[i-1]∈\{'.',s[j]\}\ \ \&\& \ \ dp[i][j-1]) & p[i]=='*' \\ p[i]∈\{'.',s[j]\} \ \ \&\& \ \ dp[i-1][j-1] & p[i]!='*' \\ \end{cases}