给定一个字符串 (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
来源: http://www.bubuko.com/infodetail-3044906.html