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

版权声明: 本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址
http://blog.csdn.net/lzuacm。

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

在线提交

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

题目描述

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

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

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

说明:

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

示例 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

• 通过次数：1.9K
• 提交次数：10.5K

• 贡献者：LeetCode

• 相关话题 字符串 动态规划 回溯算法
  相似题目 通配符匹配

分析

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

克莱尼星号(算子)

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

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

定义及标记法

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

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

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

例子

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 $\forall a,b\in M:a\circ b\in M$

• (结合律) ∀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 ${\displaystyle \exists ϵ\in M:\forall a\in M:a\circ ϵ=a=ϵ\circ a}$

如果 V 是 M 的子集，则 V $V$被定义为包含 ϵ $ϵ$(空字符串)并闭合于这个运算下的 V 的最小超集。接着 V $V$自身是幺半群，并被称为“ V $V$生成的自由幺半群”。这是上面讨论的 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的长度分别记作 T $T$, P $P$。 在最坏的情况下，调用match(text[i:], pattern[2j:])的次数将为 (i+ji) $(\frac{i+j}{i})$ ，将产生的字符串的时间复杂度阶数为 O(T−i) $O(T-i)$和 O(P−2⋅j) $O(P-2\cdot j)$ 。 因此，时间复杂度可表示为 ∑Ti=0∑P/2j=0(i+ji)O(T+P−i−2j) $\sum _{i=0}^T\sum _{j=0}^{P/2}(\frac{i+j}{i})O(T+P-i-2j)$。 通过本文之外的一些努力，可证明这个复杂度可规约为 O((T+P)2T+P2) $O((T+P)2^{T+\frac{P}{2}})$。
- 空间复杂度：对于每次的match调用，我们将创建上述的字符串，可能会创建重复项。 如果没有释放内存，这将总共需要的空间为 O((T+P)2T+P2) $O((T+P)2^{T+\frac{P}{2}})$，即使实际上必需的不一样 P $P$和 T $T$的后缀所占空间仅为 O(T2+P2) $O(T^2+P^2)$ 。

方法2：动态规划

由于该问题具有最优子结构 ，因此缓存中间结果是很自然的。 我们探索如何表示<kbd>dp(i, j)</kbd> ：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的长度分别记作 T $T$, P $P$。
  每次从 i=0,⋯,T;j=0,...,P $i=0,\cdots ,T;j=0,...,P$范围内dp(i, j)的调用工作做完一次，所花的时间为 O(1) $O\left(1\right)$。因此，时间复杂度是 O(T⋅P) $O(T\cdot P)$。

• 空间复杂度：该算法中使用的内存空间即为布尔值的缓存，占用的空间大小为 O(T⋅P) $O(T\cdot P)$。 因此，空间复杂度是 O(T⋅P) $O(T\cdot P)$ 。
  
  Reference:
  Regular Expression Matching - LeetCode Articles
  Kleene星号