LeetCode--044--通配符匹配(java)*
2024-10-07 11:45:41
给定一个字符串 (s
) 和一个字符模式 (p
) ,实现一个支持 '?'
和 '*'
的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
说明:
s
可能为空,且只包含从a-z
的小写字母。p
可能为空,且只包含从a-z
的小写字母,以及字符?
和*
。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输入: false
思路:
用sp和pp分别纪录s和p当前要进行匹配的位置;match纪录s中匹配到的位置,用于让sp下次从这里开始;star纪录*出现的位置,pp从*的下一个位置出发。
例 s = "abcde"
p = "*e"
过程:star = 0,match = 0,pp = 1
star!=-1 match = 1,sp = 1 pp = 1
star!=-1 match = 2,sp = 2 pp = 1
star!=-1 match = 3,sp = 3 pp = 1
e == e 跳出while循环
pp == p.length() return true
TIME:O(N)
SPACE:O(1)
class Solution {
public boolean isMatch(String s, String p) {
int sp = 0;
int pp = 0;
int star = -1;
int match = 0;
while(sp < s.length()){
if(pp < p.length() &&(s.charAt(sp) == p.charAt(pp) || p.charAt(pp) == '?')){
sp++;
pp++;
}else if(pp < p.length() && p.charAt(pp) == '*'){
star = pp;
match = sp;
pp++;
}else if(star != -1){
match++;
sp = match;
pp = star + 1;
}else return false;
}
while(pp < p.length() && p.charAt(pp) == '*'){
pp++;
}
return p.length() == pp;
}
}
2019-05-03 09:42:32
最新文章
- Java 堆内存与栈内存异同(Java Heap Memory vs Stack Memory Difference)
- 从Nodejs脚本到vue首页看开源始末的DemoHouse
- NHibernate中session.update()及session.merge()的区别
- 2015-微软预科生计划-面试题-Swimming Plans
- android studio出现Error:compileSdkVersion android-x requires compiling with JDK 7问题
- ERP产品价格成本计算的几个方法(转)
- OpenStack fuel-web不可用解决办法
- Load an X509 PEM file into Windows CryptoApi
- JavaScript高级程序设计之寄生组合式继承
- Effective Java单元测试JUnit - 就是爱Java
- linux日志查看命令
- SQL Server性能优化(9)聚集索引的存储结构
- javascript打印1-100内的质数
- VirtualBox配置
- C# byte[]和文件FileStream相互转化
- SQLSERVER查询整个数据库中某个特定值所在的表和字段的方法
- mybatis的Mapper代理原理
- Python之tornado框架原理
- CentOS6.9添加环境变量
- tkinter之canvas(画布)