[LeetCode] 10. Regular Expression Matching
2024-10-21 12:51:06
Implement regular expression matching with support for '.' and '*'.
DP:
public class Solution {
public boolean isMatch2(String s, String p) {
int starCnt = 0;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*') {
starCnt++;
}
}
boolean[] star = new boolean[p.length() - starCnt];
StringBuilder temp = new StringBuilder(p.length() - starCnt);
int index = -1;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*') {
star[index] = true;
} else {
temp.append(p.charAt(i));
star[++index] = false;
}
}
String r = temp.toString();
boolean[] lastRow = new boolean[s.length() + 1];
boolean[] curRow = new boolean[s.length() + 1];
boolean[] tempRow;
lastRow[0] = true;
for (int i = 0; i < r.length(); i++) {
if (star[i] && lastRow[0]) {
curRow[0] = true;
} else {
curRow[0] = false;
}
for (int j = 0; j < s.length(); j++) {
if (!star[i]) {
if ((r.charAt(i) == '.' || r.charAt(i) == s.charAt(j)) && lastRow[j]) {
curRow[j + 1] = true;
} else {
curRow[j + 1] = false;
}
} else {
if (lastRow[j + 1]) {
curRow[j + 1] = true;
} else if (lastRow[j] || curRow[j]) {
if (r.charAt(i) == '.' || r.charAt(i) == s.charAt(j)) {
curRow[j + 1] = true;
} else {
curRow[j + 1] = false;
}
} else {
curRow[j + 1] = false;
}
}
}
tempRow = lastRow;
lastRow = curRow;
curRow = tempRow;
}
return lastRow[lastRow.length - 1];
}
}
最新文章
- Transaction Replication6：Transaction cleanup
- SQL Server中Rowcount与@@Rowcount的用法 和set nocount on 也会更新@@Rowcount
- svn没有对号等符号的问题
- Python学习笔记10
- 本人常用的Linux bash快捷键(持续更新)
- SVN Unable to connect to a repository at URL问题解决
- JQuery基础DOM操作
- m3u8
- hdu 5277 YJC counts stars 暴力
- CSS3 新特性 开放字体格式WOFF
- 06-OC分类、协议、ARC
- Hibernate三种状态及生命周期
- 打开safari开发者选项
- PowerDesigner的安装
- eclipse 安装 ndk 组件
- BZOJ5324 JXOI2018守卫（区间dp）
- struts2请求两次即action方法执行两次
- 4.9版本的linux内核中实时时钟芯片pcf85263的驱动源码在哪里
- 橱窗布置（Flower）（动规）
- K3Cloud调用存储过程