Leetcode 10. 正则表达式匹配 - 题解

C#版 - Leetcode 10. 正则表达式匹配 - 题解 LeetCode 10. Regular Expression Matching

在线提交

https://leetcode.com/problems/regular-expression-matching/

题目描述

给定一个字符串 (s) 和一个字符模式pattern (p)。实现支持 '.' 和'*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 '.' 和'*'。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

• 题目难度：Hard
• 通过次数：1.9K
• 提交次数：10.5K
• 贡献者：LeetCode
• 相关话题 字符串 动态规划 回溯算法 相似题目 通配符匹配

分析

首先，需要提及一个概念 - 克莱尼星号Kleene Star。

克莱尼星号(算子)

Kleene 星号算子，或称Kleene 闭包，德语称Kleensche Hülle，在数学上是一种适用于字符串或符号及字元的集合的一元运算，通常被称为自由幺半群结构(free monoid construction)。当 Kleene 星号算子被应用在一个集合VVV 时，写法是 V∗V∗V^{*}。它被广泛用于正则表达式，正则表达式由Stephen Kleene引入以描述某些自动机的特征，其中*表示“零或更多”次。

如果VVV 是一组字符串，则 V∗V∗V^{*}被定义为包含空字符串ϵϵ{\epsilon}的VVV 的最小超集，并在字符串连接操作下闭合。 如果VVV 是一组符号或字符，则 V∗V∗V^{*}是VVV 中符号上所有字符串的集合，包括空字符串ϵϵ{\epsilon}。 集合 V∗V∗V^{*}也可以描述为可以通过连接VVV的任意元素生成的有限长度字符串集合，允许多次使用相同的元素。 如果VVV 是空集ϕϕ\phi或单子集ϵϵ{\epsilon}，则V∗={ϵ}V∗={ϵ}V^{*}=\{\epsilon \}; 如果VVV 是任何其他有限集，则 V∗V∗V^{*}是可数无限集。 该算子用于生成语法或重写规则。

定义及标记法

假定 V0={ϵ}V0={ϵ}V_{0}=\{\epsilon \}, 其中ϵϵ{\epsilon}是空字符串。 递归的定义集合 Vi+1={wv:w∈Vi∧v∈V}Vi+1={wv:w∈Vi∧v∈V}{V_{i+1}=\{wv:w\in V_{i}\wedge v\in V\}\,} , 这里的 i>0i>0 i>0,

如果VVV是一个形式语言，集合VVV的第 iii次幂是集合 VVV 同自身的 i 次串接的简写。就是说，ViViV_{i}可以被理解为是从 VVV 中的符号形成的所有长度为 iii 的字符串的集合。

所以在 VVV上的 Kleene 星号运算的定义是 V∗=⋃+∞i=0Vi={ε}∪V∪V2∪V3∪…V∗=⋃i=0+∞Vi={ε}∪V∪V2∪V3∪…{ V^{*}=\bigcup _{i=0}^{+\infty }V_{i}=\left\{\varepsilon \right\}\cup V\cup V^{2}\cup V^{3}\cup \ldots }。就是说，它是从VVV中的符号生成的所有可能的有限长度的字符串的搜集。

例子

Kleene 星号算子应用于字符串集合的例子： {“ab”, “c”}* = {ε, “ab”, “c”, “abab”, “abc”, “cab”, “cc”, “ababab”, “ababc”, “abcab”, “abcc”, “cabab”, “cabc”, “ccab”, “ccc”, …} Kleene 星号应用于字元集合的例子： {‘a’, ‘b’, ‘c’}* = {ε, “a”, “b”, “c”, “aa”, “ab”, “ac”, “ba”, “bb”, “bc”, …}

推广

Kleene 星号经常推广到任何幺半群 (M, ∘∘ \circ)，也就是，一个集合 M 和在 M 上的二元运算 ∘∘ \circ 有着:

• (闭包) ∀a,b∈M: a∘b∈M∀a,b∈M: a∘b∈M\forall a,b\in M:~a\circ b\in M
• (结合律) ∀a,b,c∈M: (a∘b)∘c=a∘(b∘c)∀a,b,c∈M: (a∘b)∘c=a∘(b∘c)\forall a,b,c\in M:~(a\circ b)\circ c=a\circ (b\circ c)
• (单位元) ∃ϵ∈M: ∀a∈M: a∘ϵ=a=ϵ∘a∃ϵ∈M: ∀a∈M: a∘ϵ=a=ϵ∘a{\displaystyle \exists \epsilon \in M:~\forall a\in M:~a\circ \epsilon =a=\epsilon \circ a}

如果 V 是 M 的子集，则VVV被定义为包含ϵϵ{\epsilon}(空字符串)并闭合于这个运算下的 V 的最小超集。接着VVV自身是幺半群，并被称为“VVV生成的自由幺半群”。这是上面讨论的 Kleene 星号的推广，因为在某个符号的集合上所有字符串的集合形成了一个幺半群(带有字符串串接作为二元运算)。

方法1：递归

如果没有Kleene星号(正则表达式的 * 通配符)，问题会更容易一些 - 我们只需从左到右检查text的每个字符是否与模式pattern匹配。

当存在*时，我们可能需要检查text的许多不同后缀，看它们是否与模式pattern的其余部分匹配。 递归解法是表示这种关系的直接方法。

算法

如果没有Kleene星号，相应的Python代码将如下：

def match(text, pattern):
    if not pattern: return not text
    first_match = bool(text) and pattern[0] in {text[0], '.'}
    return first_match and match(text[1:], pattern[1:])

如pattern中存在*，则它将处于第二位置 pattern[1] 。 然后，我们可以忽略模式pattern的这一部分，或删除text中的匹配字符。 如果在任何这些操作之后我们在剩余的字符串上能匹配上，则初始输入是匹配的。相应的Java代码如下：

class Solution {
    public boolean isMatch(String text, String pattern) {
        if (pattern.isEmpty()) return text.isEmpty();
        boolean first_match = (!text.isEmpty() &&
                               (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

        if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
            return (isMatch(text, pattern.substring(2)) ||
                    (first_match && isMatch(text.substring(1), pattern)));
        } else {
            return first_match && isMatch(text.substring(1), pattern.substring(1));
        }
    }
}

复杂度分析 - 时间复杂度：将text和模式pattern的长度分别记作 TTT, PPP。 在最坏的情况下，调用match(text[i:], pattern[2j:])的次数将为 (i+ji)(i+ji)\binom{i+j}{i} ，将产生的字符串的时间复杂度阶数为 O(T−i)O(T−i)O(T - i)和 O(P−2⋅j)O(P−2⋅j)O(P - 2\cdot j) 。 因此，时间复杂度可表示为 ∑Ti=0∑P/2j=0(i+ji)O(T+P−i−2j)∑i=0T∑j=0P/2(i+ji)O(T+P−i−2j)\sum_{i = 0}^T \sum_{j = 0}^{P/2} \binom{i+j}{i} O(T+P-i-2j)。 通过本文之外的一些努力，可证明这个复杂度可规约为 O((T+P)2T+P2)O((T+P)2T+P2)O\big((T+P)2^{T + \frac{P}{2}}\big)。 - 空间复杂度：对于每次的match调用，我们将创建上述的字符串，可能会创建重复项。 如果没有释放内存，这将总共需要的空间为O((T+P)2T+P2)O((T+P)2T+P2) O\big((T+P)2^{T + \frac{P}{2}}\big)，即使实际上必需的不一样 PPP和 TTT的后缀所占空间仅为O(T2+P2)O(T2+P2)O(T^2 + P^2) 。

方法2：动态规划

由于该问题具有最优子结构 ，因此缓存中间结果是很自然的。 我们探索如何表示dp(i, j) ：text[i:]和pattern[j:] 能否匹配上？ 我们可以使用较短字符串的问题的解来表示当前字符串的解。

算法

我们继续进行与方法1相同的递归，除非因为调用只会用到match(text[i:], pattern[j:]) ，我们才使用dp(i, j) 来处理这些调用，省去了代价很高的字符串构建操作，且允许我们缓存中间结果。用Java实现的代码如下：

自底向上的方式(归纳法):

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

自顶向下的方式(演绎法):

enum Result {
    TRUE, FALSE
}

class Solution {
    Result[][] memo;

    public boolean isMatch(String text, String pattern) {
        memo = new Result[text.length() + 1][pattern.length() + 1];
        return dp(0, 0, text, pattern);
    }

    public boolean dp(int i, int j, String text, String pattern) {
        if (memo[i][j] != null) {
            return memo[i][j] == Result.TRUE;
        }
        boolean ans;
        if (j == pattern.length()){
            ans = i == text.length();
        } else{
            boolean first_match = (i < text.length() &&
                                   (pattern.charAt(j) == text.charAt(i) ||
                                    pattern.charAt(j) == '.'));

            if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                ans = (dp(i, j+2, text, pattern) ||
                       first_match && dp(i+1, j, text, pattern));
            } else {
                ans = first_match && dp(i+1, j+1, text, pattern);
            }
        }
        memo[i][j] = ans ? Result.TRUE : Result.FALSE;
        return ans;
    }
}

自底向上的分析，是从具体到抽象，比如 已知数学公式，基于公式来coding，属于演绎法；自顶向下的分析，是从抽象到具体，属于归纳法。

自底向上：

自底向上就是已经知道了所有递归边界，把所有可能的状态都算出来。基本步骤是一个拓扑排序的过程，从所有递归边界出发，当一个状态被所有可能的下层状态更新后，就用这个状态去更新后面的状态。直到所求的状态被彻底更新完成为止。

通俗地讲就是：从初始已知的状态出发，向外拓展，最后到达目标状态。

自顶向下:

自顶向下就是不考虑整个树结构，直接从要求的状态开始展开式子，如果式子中的某个状态的值还不清楚，就递归的从这个状态展开。递归结束后式子中的状态都被对应的值替换了，所求状态自然也就清楚了。

通俗地讲就是：从最终状态开始，找到可以到达当前状态的状态，如果该状态还没处理，就先处理该状态。

复杂度分析

• 时间复杂度：将text和模式pattern的长度分别记作 TTT, PPP。 每次从 i=0,⋯,T;j=0,...,Pi=0,⋯,T;j=0,...,P i=0, \cdots, T; j=0, ... ,P范围内dp(i, j)的调用工作做完一次，所花的时间为O(1)O(1)O(1)。因此，时间复杂度是 O(T⋅P)O(T⋅P)O(T\cdot P)。
• 空间复杂度：该算法中使用的内存空间即为布尔值的缓存，占用的空间大小为O(T⋅P)O(T⋅P)O(T\cdot P)。 因此，空间复杂度是 O(T⋅P)O(T⋅P)O(T\cdot P) 。 Reference: Regular Expression Matching - LeetCode Articles Kleene星号