☆打卡算法☆LeetCode 10、实现正则表达式匹配 算法解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: “给定一个字符串,以及字符规律,实现一个正则表达式匹配。”

一、题目


1、算法题目

“给定一个字符串,以及字符规律,实现一个正则表达式匹配。”

题目链接: 来源:力扣(LeetCode)

链接:leetcode-cn.com/problems/re…


2、题目描述

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

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

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

比如:

示例 1:
输入:s = "aa" p = "a"<br>
输出:false<br>
解析: "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"。
复制代码


二、解题


1、思路分析

这道题,可以使用动态规划算法,题目中的匹配是一个逐步匹配的过程,每次从匹配规则中取出一个字符,然后在字符串中匹配。

对于匹配规则来说,如果是单一字符,那么匹配方法具有唯一性,比如 a 就只能匹配 a

如果是字符组合,比如 a* ,它可以在字符串中匹配任意自然数个字符,并不具有唯一性,因此使用动态规划,对匹配方案进行枚举。


2、代码实现

直接来看一下图,s="abbbc",p="abbc".

网络异常,图片无法展示
|

true表示这个字符是匹配的,比如table[0,0]为true,表示s[0:0]="a"与p[0:0]="a"匹配。

接着,从右下角出发,去找下一个匹配位置,也就是:

table[4,6] 到 table[4,4] A

table[3,1] 到 table[2,1] B

table[1,1] 到 table[0,0] C

这三条走向分别进行回溯,然后使用table做备忘录,避免重复计算。

计算table每个格子的值时,先让右下角为true,然后依次计算格子值,直到左上角,则表示s与p匹配。

自顶向下的动态规划 类似于回溯法,参考代码:

public class Solution 
{
    public bool IsMatch(string s, string p) 
    {
        bool[,] dp = new bool[s.Length + 1, p.Length + 1];
        dp[s.Length, p.Length] = true;
        for (int i = s.Length; i >= 0; i--)
        {
            for (int j = p.Length - 1; j >= 0; j--)
            {
                bool first_match = (i < s.Length && (p[j] == s[i] || p[j] == '.'));
                if (j + 1 < p.Length && p[j + 1] == '*')
                {
                    dp[i, j] = dp[i, j + 2]    //A
                        || first_match && dp[i + 1, j]; //B
                }
                else
                {
                    dp[i, j] = first_match && dp[i + 1, j + 1]; // C
                }
            }
        }
        return dp[0, 0];
    }
}
复制代码

网络异常,图片无法展示
|


3、时间复杂度

时间复杂度 : O(sLen*pLen)

table中每个值会被计算一次,不会重复计算,而每个格子的计算时间可认为是O(1),所以总时间复杂度为O(sLen*pLen)

空间复杂度: O(sLen*pLen)

able空间复杂度为 O(sLen*pLen).


三、总结

看官方的动态规划,思路很清晰,只要填个表就能解决问题。



相关文章
|
3月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
56 0
|
3月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
62 3
|
3月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
49 0
|
4天前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
29天前
|
机器学习/深度学习 人工智能 算法
深入解析图神经网络:Graph Transformer的算法基础与工程实践
Graph Transformer是一种结合了Transformer自注意力机制与图神经网络(GNNs)特点的神经网络模型,专为处理图结构数据而设计。它通过改进的数据表示方法、自注意力机制、拉普拉斯位置编码、消息传递与聚合机制等核心技术,实现了对图中节点间关系信息的高效处理及长程依赖关系的捕捉,显著提升了图相关任务的性能。本文详细解析了Graph Transformer的技术原理、实现细节及应用场景,并通过图书推荐系统的实例,展示了其在实际问题解决中的强大能力。
154 30
|
8天前
|
存储 监控 算法
企业内网监控系统中基于哈希表的 C# 算法解析
在企业内网监控系统中,哈希表作为一种高效的数据结构,能够快速处理大量网络连接和用户操作记录,确保网络安全与效率。通过C#代码示例展示了如何使用哈希表存储和管理用户的登录时间、访问IP及操作行为等信息,实现快速的查找、插入和删除操作。哈希表的应用显著提升了系统的实时性和准确性,尽管存在哈希冲突等问题,但通过合理设计哈希函数和冲突解决策略,可以确保系统稳定运行,为企业提供有力的安全保障。
|
1月前
|
存储 算法
深入解析PID控制算法:从理论到实践的完整指南
前言 大家好,今天我们介绍一下经典控制理论中的PID控制算法,并着重讲解该算法的编码实现,为实现后续的倒立摆样例内容做准备。 众所周知,掌握了 PID ,就相当于进入了控制工程的大门,也能为更高阶的控制理论学习打下基础。 在很多的自动化控制领域。都会遇到PID控制算法,这种算法具有很好的控制模式,可以让系统具有很好的鲁棒性。 基本介绍 PID 深入理解 (1)闭环控制系统:讲解 PID 之前,我们先解释什么是闭环控制系统。简单说就是一个有输入有输出的系统,输入能影响输出。一般情况下,人们也称输出为反馈,因此也叫闭环反馈控制系统。比如恒温水池,输入就是加热功率,输出就是水温度;比如冷库,
272 15
|
3月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
2月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
75 4

推荐镜像

更多