【leetcode】10.Regular Expression Matching
2024-10-16 18:42:35
题目描述：
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
解题思路：
这道题如果只考虑“.”的话其实很好完成，所以解题的关键在于处理“*”的情况。以为“*”与前一个字母有关，所以应该整体考虑ch*……的情况。ch*可以匹配0-n个s的字符串，(n是s的起始位置开始值为ch的字符的个数)。当然还要考虑.*……的情况，这样的情况系，就要考虑把.*与s的所有字符都匹配一遍，看能不能找出结果。其他的考虑情况比较容易想到，看下面的代码即可。
具体代码：
public static boolean isMatch(String s, String p) {
//p为null或者长度为0的情况
if(p==null){
return s==null;
}
if(p.length()==0){
return s.length()==0;
}
if(p.length()==1){
if(s.length()!=1){
return false;
}
else{
if(p.charAt(0)=='.'){
return true;
}
else if(p.charAt(0)=='*'){
return false;
}
else{
return p.charAt(0)==s.charAt(0);
}
}
}
//p至少有长度为2
if(p.contains("*")|| p.contains(".")){
//ch*情况的处理
if(p.charAt(1)=='*'){
char ch = p.charAt(0);
//.*的情况，.*可以匹配s的任意个字符，所以把每种可能的情况递归一遍
if(ch=='.'){
for(int i=0;i<=s.length();i++){
boolean key = isMatch(s.substring(i), p.substring(2));
if(key==true)
return true;
}
}
//ch*的情况，ch*可以匹配0-n个s的字符串，(n是s的起始位置开始值为ch的字符的个数)
else{
int index=0;
while(index<s.length() && s.charAt(index)==p.charAt(0)){
index++;
}
for(int i=0;i<=index;i++){
boolean key = isMatch(s.substring(i), p.substring(2));
if(key==true)
return true;
}
}
}
//不是ch*的情况，即chch……的情况，这时候s的长度要保证大于0
else{
if(p.charAt(0)=='.'){
if(s.length()==0){
return false;
}
boolean key = isMatch(s.substring(1), p.substring(1));
return key;
}
else{
if(s.length()==0){
return false;
}
//如果开头字符相等，匹配与否取决于两字符串除去第一个字符后是否匹配
if(p.charAt(0)==s.charAt(0)){
boolean key = isMatch(s.substring(1), p.substring(1));
return key;
}
else{
return false;
}
}
}
return false;
}
//p不包含*，.的情况
else{
if(s.equals(p))
return true;
return false;
}
}
最新文章
- 安卓真机调试 出现Installation error: INSTALL_FAILED_UPDATE_INCOMPATIBLE....
- 基于CkEditor实现.net在线开发之路（4）快速布局，工具箱，模板载入，tab选项卡简单说明与使用
- android--访问网络权限
- [转载]Grunt插件之LiveReload 实现页面自动刷新，所见即所得编辑
- 无废话SharePoint入门教程五[创建SharePoint页面布局]
- angular的uiRouter服务学习(5) --- $state.includes()方法
- java CyclicBarrier
- Linux红帽认证----I Want
- mysql查询区分大小写与自定义排序
- JSON字符串序列化与反序列化浅试
- HTML5 WebAudioAPI-实例(二)
- [置顶] SSO单点登录系列6：cas单点登录防止登出退出后刷新后退ticket失效报500错
- C#把gird数据导出到excel
- DOM4J生成、解析XML实例
- 将pandas的Dataframe对象读写Excel文件
- [转] js实现对图片的二进制流md5计算
- 26. 天马tomcat授权文件的影响因素
- VIM 插入
- 北京Uber优步司机奖励政策（4月15日）
- Linux Deploy 使用 Repository部署Linux系统