当前位置:网站首页>leetcode 10. Regular Expression Matching 正则表达式匹配 (困难)
leetcode 10. Regular Expression Matching 正则表达式匹配 (困难)
2022-07-05 13:02:00 【InfoQ】
一、题目大意
- 1 <= s.length <= 20
- 1 <= p.length <= 30
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母,以及字符 . 和 *。
- 保证每次出现字符 * 时,前面都匹配到有效的字符
二、解题思路
三、解题方法
3.1 Java实现
public class Solution2 {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1; i < n + 1; i++) {
if (p.charAt(i - 1) == '*') {
// 星号 不会在第1个位置
dp[0][i] = dp[0][i - 2];
}
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
// 上个通配符可能是 点号、星号、字符
if (p.charAt(j - 1) == '.') {
// 上个通配符是 点号
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) != '*') {
// 上个通配符不是 星号
dp[i][j] = dp[i - 1][j - 1] && p.charAt(j - 1) == s.charAt(i - 1);
} else if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
dp[i][j] = dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i][j - 2];
}
}
}
return dp[m][n];
}
}
四、总结小记
- 2022/7/5 上行下效,皇帝的新装
边栏推荐
- LB10S-ASEMI整流桥LB10S
- Put functions in modules
- RHCSA7
- SAP UI5 DynamicPage 控件介紹
- Halcon template matching actual code (I)
- Developers, is cloud native database the future?
- MySQL 巨坑:update 更新慎用影响行数做判断!!!
- C# 对象存储
- Shi Zhenzhen's 2021 summary and 2022 outlook | colorful eggs at the end of the article
- Notion 类笔记软件如何选择?Notion 、FlowUs 、Wolai 对比评测
猜你喜欢
解决uni-app配置页面、tabBar无效问题
SAP SEGW 事物码里的 ABAP Editor
Navigation property and entityset usage in SAP segw transaction code
Fragmented knowledge management tool memos
leetcode:221. Maximum square [essence of DP state transition]
DataPipeline双料入选中国信通院2022数智化图谱、数据库发展报告
Changing JS code has no effect
Leetcode20. Valid parentheses
“百度杯”CTF比赛 九月场,Web:SQL
DataPipeline双料入选中国信通院2022数智化图谱、数据库发展报告
随机推荐
Halcon 模板匹配实战代码(一)
SAP UI5 视图里的 OverflowToolbar 控件
Small case of function transfer parameters
HiEngine:可媲美本地的云原生内存数据库引擎
Datapipeline was selected into the 2022 digital intelligence atlas and database development report of China Academy of communications and communications
手把手带你入门Apache伪静态的配置
leetcode:221. Maximum square [essence of DP state transition]
APICloud Studio3 API管理与调试使用教程
SAP UI5 DynamicPage 控件介绍
Apicloud studio3 API management and debugging tutorial
mysql econnreset_ Nodejs socket error handling error: read econnreset
Binder通信过程及ServiceManager创建过程
【每日一题】1200. 最小绝对差
无密码身份验证如何保障用户隐私安全?
Android本地Sqlite数据库的备份和还原
Talking about fake demand from takeout order
潘多拉 IOT 开发板学习(HAL 库)—— 实验7 窗口看门狗实验(学习笔记)
SAP SEGW 事物码里的 ABAP 类型和 EDM 类型映射的一个具体例子
解决uni-app配置页面、tabBar无效问题
Rocky基础知识1