正则表达式匹配

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，10.Regular Expression Matching

先看题目描述

大概就是给两个字符串，一个是原字符串，一个是正则表达式，判断是否匹配

算法思路

因为这道题自己一直没想出来，就直接去看了题解，才看明白，下面是那篇题解

使用的方法是动态规划

状态

dp[i][j] 表示 s 的前 i 个字符是否能与 p 的前 j 个匹配

状态转移方程

已知 dp[i-1][j-1]，要求 dp[i][j]，根据 s[i]，p[j] 值的不同，要分情况考虑

  • 当 s[i] = p[j] 或 p[j] = “.”时，dp[i][j] = dp[i-1][j-1]

  • 当 p[j] = “*”时，因为 * 的含义是匹配零个或多个前面的那个元素，所以要考虑前面的元素 p[j-1]

    • 当 p[j - 1] != s[i] 时，dp[i][j] = dp[i][j-2]，比如(ab, abc)，遇到 * 往前看两个，发现前面 s[i] 的 ab 和 p[j-2] 的 ab 能匹配，虽然后面有 c，但可以看作 c 重复 0 次，所以也是 true
    • 当 p[j-1] = s[i] 或 p[j-1] = “.” 时，又有两种情况
      • p[j-1] 重复 0 次，dp[i][j] = dp[i][j-2]
      • p[j-1] 重复多次，dp[i][j] = dp[i-1][j]
      • 两种满足一种就能匹配上

实际上看的题解中还有 p[j-1] 重复一次的情况，但是实际上这种情况是多余的，因为检查多个字符匹配的时候也是要落到检查单个字符最后检查 empty，也可以这样理解，重复一次的情况时，dp[i][j] = dp[i][j-1]，由于 p[j-1] 是字母或 “.”，必然可以推到 dp[i][j] = dp[i-1][j-2]，又由于 p[j] 是 “*”，则得到 dp[i][j] = dp[i-1][j]

找到状态转移方程以后就是一些细节和初始化 dp 的问题了

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isMatch(String s, String p) {
        s = " " + s;
        p = " " + p;
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                if(p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}