10. 正则表达式匹配

Last updated 18 days ago

10. 正则表达式匹配

题目描述

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

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

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

示例 1：

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

示例 2:

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

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

提示：

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符。

题解

两套做法，特定针对这道题的 DP 方法和正则表达式匹配实现的一般方式。第二种很复杂，可以看看这个题解了解一下。这里主要针对第一种方法给出题解。

这个问题是使用动态规划的一个经典问题，状态表示使用 f[i][j]（i <= n, j <= m），表示 s[i...end] 和 p[j...end] 两个字符串是否能匹配成功。分成几种情况来看：

若 s[i] == p[j] || p[j] == '.' 且 p[j + 1] != '*'，那么表示当前位置匹配，我们只需要去看下一个位置是否匹配即可，即 f[i][j] = (p[j] == '.' || s[i] == p[j]) && match(i + 1, j + 1)。
若 p[j + 1] == '*'，那 '*' 对应的可能是 0 个或是多个 p[j] 字符，则有 f[i][j] = match(i, j + 2) || ((p[j] == '.' || s[i] == p[j]) && match(i + 1, j))。match(i, j + 2) 表示匹配 0 个，后半部分表示匹配多个，而匹配多个可以是逐个匹配，因此匹配 i + 1 的位置即可。
处理边界情况：当 s[i...end] 和 p[j...end] 均为空串时，匹配成功 f[n][m] = true；当子串匹配结束时 j == m，目标串也应该匹配到结束 i == n。

为了避免在匹配时重复搜索 f[i][j] 使用记忆化搜索进行优化。

C++

class Solution {
public:
    vector<vector<int>> f;
    bool match(int i, int j, const string &s, const string &p) {
        if (f[i][j] != -1) {
            return f[i][j];
        }
        else if (j == p.size()) {
            f[i][j] = (i == s.size());
            return f[i][j];
        }
        bool first_match = i < s.size() && (p[j] == '.' || (s[i] == p[j]));
        if (p[j + 1] == '*' && j + 1 < p.size()) {
            f[i][j] = match(i, j + 2, s, p) || (first_match && match(i + 1, j, s, p));
        }
        else {
            f[i][j] = first_match && match(i + 1, j + 1, s, p);
        }
        return f[i][j];
    }
    bool isMatch(string s, string p) {
        f = vector<vector<int>>(s.size() + 1, vector<int>(p.size() + 1, -1));
        f[s.size()][p.size()] = 1;
        return match(0, 0, s, p);
    }
};

func boolToint(x bool) int {
    if x {
        return 1
    } else {
        return 0
    }
}

func match(i, j int, s, p string, f [][]int) bool {
    if (f[i][j] != -1) {
        return f[i][j] != 0
    } else if (j == len(p)) {
        if (i == len(s)) {
            f[i][j] = 1
        } else {
            f[i][j] = 0
        }
        return f[i][j] != 0
    }
    first_match := (i < len(s)) && (p[j] == '.' || s[i] == p[j])
    if j + 1 < len(p) && p[j + 1] == '*' {
        f[i][j] = boolToint(match(i, j + 2, s, p, f) || (first_match && match(i + 1, j, s, p, f)))
    } else {
        f[i][j] = boolToint(first_match && match(i + 1, j + 1, s, p, f))
    }
    return f[i][j] != 0
}

func isMatch(s string, p string) bool {
    n, m := len(s), len(p)
    f := make([][]int, n + 1)
    for i := range f {
        f[i] = make([]int, m + 1)
        for j := 0; j <= m; j++ {
            f[i][j] = -1
        }
    }
    f[n][m] = 1
    return match(0, 0, s, p, f)
}

知识点

Go 中的数组（array）不支持动态大小，例如，[n][m]int 这种形式。
Go 种二维切片的声明与初始化方式。
Go 中的 int 和 bool 不能直接相互转换，需要借助判断或是函数实现转换。
记忆化搜索优化。

Previous1. 两数之和