关键词:
10. 正则表达式匹配
给你一个字符串 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
解释: ".*" 表示可匹配零个或多个(‘*‘)任意字符(‘.‘)。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 ‘*‘ 表示零个或多个,这里 ‘c‘ 为 0 个, ‘a‘ 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
class Solution:
def isMatch(self, s: str, p: str) -> bool:
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[-1][-1] = True
for i in range(len(s), -1, -1):
for j in range(len(p) - 1, -1, -1):
first_match = i < len(s) and p[j] in s[i], ‘.‘
if j+1 < len(p) and p[j+1] == ‘*‘:
dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
else:
dp[i][j] = first_match and dp[i+1][j+1]
return dp[0][0]
力扣练习题(代码片段)
每日一练力扣1209.删除字符串中的所有相邻重复项II力扣1047.删除字符串中的所有相邻重复项力扣76.最小覆盖子串剑指OfferII039.直方图最大矩形面积力扣1209.删除字符串中的所有相邻重复项II给你一个字符串s,「k倍重复项删除... 查看详情
力扣练习题(代码片段)
每日一练力扣1209.删除字符串中的所有相邻重复项II力扣1047.删除字符串中的所有相邻重复项力扣76.最小覆盖子串剑指OfferII039.直方图最大矩形面积力扣1209.删除字符串中的所有相邻重复项II给你一个字符串s,「k倍重复项删除... 查看详情
力扣练习006---前k个高频单词(692)(代码片段)
题目描述:https://leetcode-cn.com/problems/top-k-frequent-words/submissions/ 给一非空的单词列表,返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排... 查看详情
leetcode(二分查找法)入门练习一(代码片段)
...0c;如果目标值存在返回下标,否则返回-1。来源:力扣(LeetCode)链接:https:// 查看详情
力扣-2020年最后一次登录(代码片段)
...家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。文章目录前言一、题目:1890.2020年最后一次登录二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示... 查看详情
力扣练习3(十题)(代码片段)
1.(1436) 旅行终点站给你一份旅游线路图,该线路图中的旅行线路用数组paths表示,其中paths[i]=[cityAi,cityBi]表示该线路将会从cityAi直接前往cityBi。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线... 查看详情
力扣练习2(十题)(代码片段)
目录1.删除有序数组中的重复项2.移除元素 3.搜索插入位置 4.实现strStr()5.(6)Z字形变换 6.(19) 删除链表的倒数第N个结点7.(23) 合并K个升序链表8.(25) K个一组翻转链表9.(58)最后一个单词的长度10.(66)加一1.删除有序数组中的重复项... 查看详情
力扣练习2(十题)(代码片段)
目录1.删除有序数组中的重复项2.移除元素 3.搜索插入位置 4.实现strStr()5.(6)Z字形变换 6.(19) 删除链表的倒数第N个结点7.(23) 合并K个升序链表8.(25) K个一组翻转链表9.(58)最后一个单词的长度10.(66)加一1.删除有序数组中的重复项... 查看详情
力扣练习004---二叉树的层次遍历(102)(代码片段)
题目描述:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。例如:给定二叉树: [3,9,20,null,null,15,7],3/920/157返回其层次遍历结果:[[3],[9,2... 查看详情
力扣题目46-全排列+47-全排列ii
题目题解46.一看这个题目发现和 力扣题目31--下一个排列 类似一个是找下一个一个是找全部那么我们把一开始nums进行排序从小到大然后循环31题的题解加入vector<vector<int>>res;如果i为-1则退出循环即可47.同上代码461... 查看详情
力扣-第二高的薪水(代码片段)
...家好,我是空空star,本篇带大家了解一道中等的力扣sql练习题。文章目录前言一、题目:176.第二高的薪水二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④... 查看详情
算法练习题力扣练习题——数组:在有序数组中查找元素存在的范围(代码片段)
原题说明:给定一个按照升序排列的整数数组nums,和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(logn)级别。如果数组中不存在目标值,返回 [-1,-1]。原题链接:https://l... 查看详情
力扣每日一题934.最短的桥难度:中等,rating:1825(dfs/bfs)(代码片段)
文章目录题目链接思路一(两次dfs)代码一思路二(一次dfs+一次bfs)代码二题目链接https://leetcode.cn/problems/shortest-bridge/题目来源于:第109场周赛Q3rating:1825思路一(两次dfs)题目要求的实际上是两个... 查看详情
练习题目及答案)(代码片段)
文章目录一、数据库概述练习题二、MySQL环境搭建练习题三、查询练习MySQL数据库练习题(包含前5章所有知识点及答案)前置知识:一、数据库开发与实战专栏导学及数据库基础概念入门二、MySQL介绍及MySQL安装与配置三、MySQL数... 查看详情
力扣-进店却未进行过交易的顾客(代码片段)
...家好,我是空空star,本篇带大家了解一道简单的力扣sql练习题。文章目录前言一、题目:1581.进店却未进行过交易的顾客二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果... 查看详情
java自除数——力扣每日一题(2022.03.31)
目录题目:728.自除数方法一:暴力一直走,天总会亮。题目:728.自除数728.自除数本题链接(点击直接跳转)https://leetcode-cn.com/problems/self-dividing-numbers//方法一:暴力packagedaily;importjava.util.Arra 查看详情
java自除数——力扣每日一题(2022.03.31)(代码片段)
目录题目:728.自除数方法一:暴力一直走,天总会亮。题目:728.自除数728.自除数本题链接(点击直接跳转)https://leetcode-cn.com/problems/self-dividing-numbers//方法一:暴力packagedaily;importjava.util.Arra 查看详情
力扣练习4(十题)(代码片段)
1.(412) FizzBuzz给你一个整数n,找出从1到n各个整数的FizzBuzz表示,并用字符串数组answer(下标从1开始)返回结果,其中:answer[i]=="FizzBuzz"如果i同时是3和5的倍数。answer[i]== 查看详情