萤火小屋

优律的知识库

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

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

力扣10题-正则表达式匹配

发表于 2021-04-20 | 分类于 力扣刷题 | 0 | 阅读次数 244

题目描述

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持'.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符
'*'匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

样例

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

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

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

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

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

  • 提示:
    0 <= s.length <= 20
    0 <= p.length <= 30
    s 可能为空,且只包含从 a-z 的小写字母。
    p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
    保证每次出现字符 * 时,前面都匹配到有效的字符

题目评估

知识点:动态规划
难度:困难(真的好难,呜呜呜~)

分析

这题给我整蒙了,目前还没有完全透彻的搞懂,放个官方题解吧。

Java代码题解

class Solution {
    public boolean isMatch(String s, String p) {
		
    	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    	
    	dp[0][0] = true;  // s和p长度都为0匹配成功
    	
    	// 注意:这里i从0开始,即使s长度为0也可能匹配成功
    	for (int i = 0; i < dp.length; i++) {
			
    		// 注意:这里j从1开始,因为p长度为0,如果s长度不为0,一定匹配失败
    		for (int j = 1; j < dp[i].length; j++) {
    			
    			if (p.charAt(j - 1) == '*') {  // 如果当前p[j]为*
    				
    				if (match(s, p, i, j - 1)) {  // 看一下s[i]和p[j-1]是否一样
    					// 如果它们一样,p中*前边的字符在s中多次出现的 或 在s中只出现一次
    					dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
    				} else {
    					// 如果*前字符不匹配,直接不管“字符+*”的组合,返回上一个字符串的匹配结果
    					dp[i][j] = dp[i][j - 2];
    				}
    				
    			} else {  // p[j]不是*
    				if (match(s, p , i ,j)) {  // 匹配一下s[i]和p[j]是否一样
    					// 掐掉当前头后的字符串后的匹配情况和当前字符串的匹配情况相同
    					dp[i][j] = dp[i - 1][j - 1];
    				} else {
    					dp[i][j] = false;  // 如果当前字符都不一样,直接false
    				}
    			}
    						
			}
    		
		}
    	
    	return dp[dp.length - 1][dp[0].length - 1];
    }
    
    private boolean match(String s, String p, int i, int j) {
    	
    	if (i == 0) {  // 如果s长度为0直接返回false
    		return false;
    	} else if (p.charAt(j - 1) == '.') {  // ‘.’匹配任何字符
    		return true;
    	} else {
    		return s.charAt(i - 1) == p.charAt(j - 1);	
    	}
    	
    }
    
}
力扣10题

复杂度分析

设n为s字符串的长度,m为p字符串的长度,双层遍历两个字符串,时间复杂度为:O(nm),由于开辟了一个n+1行m+1列的数组,所以空间复杂度为O(nm)。

# 算法 # 程序设计 # 动态规划
力扣1312题-让字符串成为回文串的最少插入次数-动态规划题解
力扣53题-最大子序和-动态规划题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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