10. Regular Expression Matching字符串.*匹配
2024-08-28 13:15:32
[抄题]:
Given an input string (s
) and a pattern (p
), implement regular expression matching with support for '.'
and '*'
.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s
could be empty and contains only lowercase lettersa-z
.p
could be empty and contains only lowercase lettersa-z
, and characters like.
or*
.
Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
[暴力解法]:
时间分析:
空间分析:
[优化后]:
时间分析:
空间分析:
[奇葩输出条件]:
[奇葩corner case]:
[思维问题]:
想不到是dp:最值、可行、个数
[一句话思路]:
写不出程序,就尝试只写公式
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- 先写一般情况,再写特殊情况,别丢了
[二刷]:
- 都是从1<x <=n开始写,请看新代码
[三刷]:
[四刷]:
[五刷]:
[五分钟肉眼debug的结果]:
[总结]:
前面的不能用,后果会遗传,是这道题和wildcard匹配的区别 dp[i][j] = dp[i][j - 2];
[复杂度]:Time complexity: O(n^2) Space complexity: O(n^2)
[英文数据结构或算法,为什么不用别的数据结构或算法]:
[关键模板化代码]:
[其他解法]:
[Follow Up]:
[LC给出的题目变变变]:
[代码风格] :
class Solution {
public boolean isMatch(String s, String p) {
//ini:dp[][], dp[0][0], dp[0][j]
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*' && dp[0][j - 2] == true) dp[0][j] = true;
} //for loop: 2 cases
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == s.charAt(i - 1) ) {
dp[i][j] = dp[i - 1][j - 1];
} if (p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
} if (p.charAt(j - 1) == '*') {
//*之前的不能用
if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
//前面的不能用,后果会遗传
dp[i][j] = dp[i][j - 2];
}else {
//匹配多个,0个,1个
dp[i][j] = dp[i - 1][j] || dp[i][j - 2] || dp[i][j - 1];
}
} }
} //return
return dp[s.length()][p.length()];
}
}
最新文章
- sga_target大于sga_max_size数据库无法启动
- [C#]Attribute特性(2)——方法的特性及特性参数
- 【读书笔记】读《高性能网站建设指南》及《高性能网站建设进阶指南:Web开发者性能优化最佳实践》
- hadoop之mapReduce踩坑集合
- eclipse3.7 安装maven插件与scm
- CUDA纹理绑定
- K60 启动过程分析
- js 数组切换图片
- vue-router路径计算问题
- JDK8 BigDecimal API-创建BigDecimal源码浅析三
- Java 中初始化 List 集合的 6 种方式!
- SpringCloud简介
- yii2.0 添加组件baidu ueditor
- 强大的vim配置文件,让编程更随意
- 【BZOJ4025】二分图(线段树分治,并查集)
- CS小分队第二阶段冲刺站立会议(5月28日)
- Android系统源代码
- 【oracle笔记2】约束
- python小知识点复习
- Jquery queue实例