萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣剑指Offer 19-正则表达式匹配

发表于 2022-08-20 | 分类于 力扣刷题 | 0 | 阅读次数 61

题目描述

请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符,而''表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"abaca"匹配,但与"aa.a"和"ab*a"均不匹配。
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
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

题目评估

官方难度:困难
知识点:递归、字符串、动态规划

分析

当年做第十题的时候觉得动态规划很难,现在依然觉得很难。不过现在看题解已经能理解了。本题用动态规划遍历子串的匹配结果,将状态保存,当遍历结束后串本身时候匹配只需要看最后一个状态即可。下边举例列了一个图。

转移方程:
当前字符是否是'*'

  1. 否:f[i][j] = f[i - 1][j - 1]
  2. 是:
    没有字符匹配:f[i][j] = f[i][j - 2]
    多个字符匹配:f[i][j] = f[i - 1][j]

image.png

Java代码题解

class Solution {
    public boolean isMatch(String s, String p) {
        int sl = s.length();
        int pl = p.length();
        boolean[][] dp = new boolean[sl + 1][pl + 1];
        // 外层遍历字符串
        for (int i = 0; i <= sl; i++) {
            // 内层遍历正则串
            for (int j = 0; j <= pl; j++) {
                // 正则串为空时,匹配串如果也为空才匹配
                if (j == 0) {
                    dp[i][j] = i == 0;
                } else {
                    // 当前正字串字符不等于*
                    if (p.charAt(j - 1) != '*') {
                        // 正常比对当前字符
                        if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                    // 当前正则串字符等于*
                    else {
                        // 当匹配串当前带*字符个数为0
                        if (j >= 2) {
                            // 把正则串的后两位当作没有
                            dp[i][j] = dp[i][j - 2];
                        }
                        // 当匹配串当前带*字符个数大于0:比对当前匹配串的最后以为和正则最后一位非*字符是否匹配
                        if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }

                    }
                }
            }
        }
        return dp[sl][pl];
    }
}

复杂度分析

匹配串长度设为m,正则串长度设为n。
时间复杂度:O(mn)
空间复杂第:O(mn)

# 算法 # 程序设计 # 动态规划
力扣剑指Offer II 041-滑动窗口的平均值
力扣第654题-最大二叉树
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持