正则匹配

正则表达式匹配

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

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

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

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

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

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

引用来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching

很可惜*的不能够单独依赖前置条件就能判断,有abccccd.跟__abc*cd__这种情况.所以终究要把多种符合匹配规则多种状态都记录下来,然后构建动态方程.

dpi 表示 s 的前 i 个是否能被 p 的前 j 个匹配

因为需要前置条件作为辅助,所以s可p为空都是符合条件的状态,而为空时候的状态我们要手动添加

• S为空,P为空状态成立
• S为空时,P不为空时,只有P为*的时候可以通过*消除前一个字符的规则获得到dp0的状态,其他都是false
• S不为空,P不为空时,肯定为false

动态方程初始值建立.然后考虑状态迁移:

对于S = [0,0] 到 S = [0,S.length] 中每一种状态我们都要计算出相应P = [0,0] 到 P = [0,P.length] 时与之对应的状态,因为每种状态都可能为之后判定的前置条件

对于一个新正则值P[j] 为如果P[j]为字符,有P[j] == S [i] 则dpi = dpi
否则dpi == false ;光一个字符成立了没用,之前也成立才是true

对于一个新正则值P[j] 为如果P[j]为.则dpi = dpi 否则dpi == false ;

对于一个新正则值P[j] 为如果P[j]为*就要判定*之前的那个字符和当前的S[i]

如果不相等通过*消除前一个字符的规则获得到dp0的状态,其他都是false

如果相等.

• dpI是True的话那dpI肯定就是True aa —> a*
• dpI是False 的话那dpI肯定就是False么?不,因为*可以删除一个,所以dpI为True的话也能为True ab —> abc*
• 还有一种情况是dpi-1为true的话,那dpI肯定就是True aa —> aa*

最后return dp[s.length][p.length];即可

        var isMatch = function (s, p) {
            var dp = Array.from(new Array(s.length + 1), () => {
                return new Array(p.length + 1)
            }); // 构建状态数组+1 因为存在空的情况做前置状态
            // dp[x][y] 代表s的前x位是否和p的前y位匹配
            dp[0][0] = true; // 空匹配空成立
            for (var i = 1; i <= p.length; i++) { //从一开始匹配
                if (p[i - 1] == '*') { //对于空字符串匹配只有*可以等同前一个状态,其他的都是错误
                    dp[0][i] = dp[0][i - 2]
                } else {
                    dp[0][i] = false;
                }
            }
            if (s.length >= 1) {
                for (var i = 1; i <= s.length; i++) {
                    dp[i][0] = false;
                }
            }
            for (var i = 1; i <= s.length; i++) {
                for (var j = 1; j <= p.length; j++) {
                    switch (p[j - 1]) {
                        case '.':
                            dp[i][j] = dp[i - 1][j - 1]
                            break;
                        case '*':
                            if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                                dp[i][j] = dp[i][j - 1] || //只多一个*  的情况成立条件是去掉这个*也能匹配
                                    dp[i - 1][j] || // 一个匹配字符加个* 的情况成立条件是前一个字符也能匹配
                                    dp[i][j - 2] // 不匹配字符加个*  的情况成立条件是去掉不匹配字符和*能匹配
                            } else {
                                dp[i][j] = dp[i][j - 2] // *消除前一个字符
                            }
                            break;
                        default:
                            if (s[i - 1] == p[j - 1]) {
                                dp[i][j] = dp[i - 1][j - 1]
                            } else {
                                dp[i][j] = false;
                            }
                            break;
                    }
                }

            }
            return dp[s.length][p.length];
        }