力扣10. 正则表达式匹配

简介: 10. 正则表达式匹配

前言

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

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

示例 1:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

样本对应模型
定义二维表
字符串有效性检查
str不能有.和*
exp开头不能是.两个不能挨着

    public static boolean isValid(char[] s, char[] e) {
        // s中不能有'.' or '*'
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '*' || s[i] == '.') {
                return false;
            }
        }
        // 开头的e[0]不能是'*',没有相邻的'*'
        for (int i = 0; i < e.length; i++) {
            if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
                return false;
            }
        }
        return true;
    }

暴力递归

递归含义:
str从si出发及其后面的所有,能不能被exp从ei出发及其后面的所有配出来
能配出来返回true,否则false
1) ei下一个位置不是*
如果ei+1不是 ,就说明我e没有操作空间了。它不能指望后面的 把它变没,代表此时si必须能和ei对上
只能是[ei]字符等于[si]字符
要么[ei]字符是 . ,它能够变成一切

2) ei+1是*
0)变零个
让a*变0个a,后面去匹配
1)变1个a
2)变2个a
3) 3个a
4) 4个a

每一种分支全都走,但有一个走通,直接返回true,所有分支都走不通,返回false,

    public static boolean isMatch1(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        return isValid(s, e) && process(s, e, 0, 0);
    }

    // str[si.....] 能不能被 exp[ei.....]配出来! true false
    public static boolean process(char[] s, char[] e, int si, int ei) {
        if (ei == e.length) { // exp 没了 str?
            return si == s.length;
        }
        // exp[ei]还有字符
        // ei + 1位置的字符,不是*
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            // ei + 1 不是*
            // str[si] 必须和 exp[ei] 能配上!
            return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
        }
        // exp[ei]还有字符
        // ei + 1位置的字符,是*!
        while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
            if (process(s, e, si, ei + 2)) {
                return true;
            }
            si++;
        }
        return process(s, e, si, ei + 2);
    }

斜率优化+记忆化搜索

image.png
f(13, 29)的依赖
image.png
f(12, 29)的依赖
f(12, 29)=f(13,29)+f(12,31)
在str中i位置字符和str中i+ 1位置字符它一样的时候就存在这个优化

当我一-个格子有枚举行为的时候,我就观察他已经算过的格子,能不能把枚举行为替代掉,
从而得到一一个使用有限若干个位置的方式来得到这一个格子的值

    public static boolean isMatch2(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        if (!isValid(s, e)) {
            return false;
        }
        int[][] dp = new int[s.length + 1][e.length + 1];
        // dp[i][j] = 0, 没算过!
        // dp[i][j] = -1 算过,返回值是false
        // dp[i][j] = 1 算过,返回值是true
        return isValid(s, e) && process2(s, e, 0, 0, dp);
    }

    public static boolean process2(char[] s, char[] e, int si, int ei, int[][] dp) {
        if (dp[si][ei] != 0) {
            return dp[si][ei] == 1;
        }
        boolean ans = false;
        if (ei == e.length) {
            ans = si == s.length;
        } else {
            if (ei + 1 == e.length || e[ei + 1] != '*') {
                ans = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process2(s, e, si + 1, ei + 1, dp);
            } else {
                if (si == s.length) { // ei ei+1 *
                    ans = process2(s, e, si, ei + 2, dp);
                } else { // si没结束
                    if (s[si] != e[ei] && e[ei] != '.') {
                        ans = process2(s, e, si, ei + 2, dp);
                    } else { // s[si] 可以和 e[ei]配上
                        ans = process2(s, e, si, ei + 2, dp) || process2(s, e, si + 1, ei, dp);
                    }
                }
            }
        }
        dp[si][ei] = ans ? 1 : -1;
        return ans;
    }
相关文章
|
6月前
|
Go
golang力扣leetcode 10.正则表达式匹配
golang力扣leetcode 10.正则表达式匹配
50 0
|
5月前
|
SQL 算法 数据挖掘
leetCode第十题 : 正则表达式匹配 动态规划【10/1000 python】
leetCode第十题 : 正则表达式匹配 动态规划【10/1000 python】
|
6月前
|
C++
leetcode-8:字符串转换整数(有限自动机(DFA)和正则表达式)
leetcode-8:字符串转换整数(有限自动机(DFA)和正则表达式)
71 1
|
6月前
|
算法 C#
Leetcode算法系列| 10. 正则表达式匹配
Leetcode算法系列| 10. 正则表达式匹配
|
算法 Python
【力扣算法03】之正则表达式匹配- python
【力扣算法03】之正则表达式匹配- python
95 0
|
算法 安全 Swift
LeetCode - #10 正则表达式匹配(前100)
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
|
Java
leetcode.10 正则表达式
leetcode.10 正则表达式
46 0
leetcode-10. 正则表达式匹配(DFS)
正则表达式是对字符串(包括普通字符(例如,a 到 z 之间的字母)和特殊字符(称为“元字符”))操作的一种逻辑公式,就是用事先定义好的一些特定字符及这些特定字符的组合,组成一个“规则字符串”,这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式,该模式描述在搜索文本时要匹配的一个或多个字符串。
57 0
leetcode-10. 正则表达式匹配(DFS)
LeetCode精讲题 10正则表达式匹配(动态规划)
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和'*'的正则表达式匹配。 '.'匹配任意单个字符 '*'匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
137 0
LeetCode精讲题 10正则表达式匹配(动态规划)
|
算法 Java C++
LeetCode(算法)- 10. 正则表达式匹配
LeetCode(算法)- 10. 正则表达式匹配
97 0
LeetCode(算法)- 10. 正则表达式匹配