（Java）心得：LeetCode——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
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

二、心得

今天的这道题非常非常非常费脑CPU~~~

我刚看时，对于示例给出的对 '*' 和 '.' 两个元字符表示疑惑，没有搞明白究竟想干嘛，可能是示例都是都是两位字符，容易造成思维定势。后来，我 Chat 了一下：

正则表达式（Regular Expression，简称正则）是一种文本模式匹配的工具。在正则表达式中，.（点号）和*（星号）是两个非常常用的元字符，用于表示匹配特定的字符或重复的字符。

1. 点号 .

定义：点号是正则表达式中的通配符，用来匹配任意一个字符（除换行符外）。

示例：

正则表达式：a.b
匹配的文本：acb、a3b、a!b 等。
不匹配的文本：ab、aabb 等。
正则表达式：.
匹配的文本：a、b、1、! 等。
不匹配的文本：空字符串或换行符。

2. 星号 *

定义：星号表示匹配前一个字符或前一个子表达式0次或多次（即重复任意多次）。

示例：

正则表达式：a*
匹配的文本：空字符串、a、aa、aaa 等。
正则表达式：ab*
匹配的文本：a、ab、abb、abbbbb 等。
不匹配的文本：空字符串、b、aa 等。
正则表达式：.*
匹配的文本：所有文本，包括空字符串。
这个表达式会匹配所有字符0次或多次，因此能匹配任何文本。

综合示例：

正则表达式：a.b*
匹配的文本：a后跟任意字符，再跟0次或多次b字符。
如：ac, ab, a, abb, acbbb等。
正则表达式：..*
匹配的文本：所有文本，因为它表示任意两个字符后跟任意字符的任意次数。
如：ab, cd, 123, !@, 等。

特殊组合示例：

正则表达式：a.*b
匹配的文本：以a开头，以b结尾，中间可以是任何字符。
如：ab、acb、a...b 等。
正则表达式：^.*$
匹配的文本：整个文本，从开头到结尾。
匹配的文本：任何字符串。
正则表达式：c.*d
匹配的文本：以c开头，以d结尾，中间可以是任何字符。
如：cd、cabd、c...d等。

通过这些示例，你可以看到.匹配任意字符，而*则允许匹配前面的字符0次或多次。这两个符号在正则表达式中非常强大，可以灵活地匹配不同的文本模式。

这样一目了然，于是我决定采用动态规划，下面是我随机举了个例子：

以 s = "abb", p = "a." 为例
dp[s][p]	'a'	'*'	'.'	'*'
'a'	1	1	0	0
'b'	0	0	1	1
'b'	0	0	1	1
1 表示 s 与 p 相匹配			0 表示 s 与 p 不匹配

慢慢捋一下应该能看懂。然而，我的思路是没有思路，并且代码实现确实很困难（对于我来说┭┮﹏┭┮）。参考一下大佬的顶级理解吧~

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length() + 1, n = p.length() + 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        for(int j = 2; j < n; j = j + 2){
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        }
        for(int i = 1; i < m; i ++){
            for(int j = 1; j < n; j ++){
                dp[i][j] = p.charAt(j - 1) == '*' ?
                dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :
                dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
            }
        }
        return dp[m - 1][n - 1];
    }
}

首先初始化 dp 矩阵，

dp[0][0] = true：代表两个空字符串能够匹配。
dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*'：首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）。因此，循环遍历字符串 p ，步长为 2（即只看偶数位）。

由于 dp[0][0] 代表的是空字符的状态，因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1] 。

当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：

dp[i][j - 2]：即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配。
dp[i - 1][j] 且 s[i - 1] = p[j - 2]：即让字符 p[j - 2] 多出现 1 次时，能否匹配。
dp[i - 1][j] 且 p[j - 2] = '.'：即让字符 '.' 多出现 1 次时，能否匹配。