leetcode 44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。
-
'?' 可以匹配任何单个字符。
-
'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。
题解:
1.一个字符串 (s) 和一个字符模式 (p)
2.'?'匹配任何单字符;'*'匹配任意字符串(包括空字符串)
3.必须完全匹配
4.两个字符串都有可能为空
示例 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
解题思路:
-
首先整理一下匹配成功的情况:
-
一是对应位置字符相同或是匹配到p种的"?"
-
二是匹配到p中的*号,"*"可以表示一个字符串或空格字符串,所以需要统计对应的是那些字符串。先让p中的工作指针跳过*号,如果s中的下一个字符跟p中跳过*的j指针指向的字符仍不匹配,就加到*号匹配的字符串中;如果匹配到*号一定改变统计指针的值,如果没改变则只有字符不匹配,直接返回false
-
当s中指针到末尾,还要检查p中指针是否到达末尾;
-
因为*号还可以表示空字符,所以可以移动指针跳过*号;除此外都要匹配s中的字符才行,而s中指针已到末尾,只需要检查p中指针是否到末尾;没到末尾,说明仍要字符匹配,不能完全匹配。到末尾,完全匹配
C/C++题解:
class Solution {
public:
bool isMatch(string s, string p) {
int i=0,j=0,istart=-1,jstart=-1,slen=s.size(),plen=p.size();
if (plen==0 || slen==0) return false;//都有可能为空
if (plen==0 && slen==0) return true;//都为空为true
//判断s的所有字符是否匹配
while (i<slen){
//字符相同或对应了"?"(?匹配任意单个字符)
if (j<plen&&(s[i]==p[j]||p[j]=='?')){
i += 1;//检查下一个
j += 1;//"*"匹配任意字符串
}else if (j<plen&&p[j]=='*'){
istart=i;//记录*匹配的s中的字符串
jstart=j;
j += 1;//j工作指针越过*,到下一个字符
}else if (istart>-1){
istart += 1; //检测到不为*,移动i指针
i=istart;//统计*匹配的字串
j=jstart+1;//统计*匹配的串时,j指针不动
}else {//字符既不相同,也没?*,只有遇到*istart指针位置变
return false; }}//不匹配
//如果匹配完s中的字符,p还剩字符,进一步判断剩下的
//如果都是*,则可以代表空字符,j工作指针往后走
while (j<plen&&p[j]=='*') j++;
//如果剩下了其它字符,j指针走不到结尾,j<plen
//则需要s中的字符去匹配,但是s已经没有字符匹配,所以false
//如果不剩,则j==plen,完全匹配
return j==plen;}};
Debug结果:
Java题解:
class Solution {
public boolean isMatch(String s, String p) {
if (p==null || s==null) return false;//都有可能为空
if (p==null && s==null) return true;//都为空为true
int i=0,j=0,istart=-1,jstart=-1,plen=p.length();
//判断s的所有字符是否匹配
while (i<s.length()){
//字符相同或对应了"?"(?匹配任意单个字符)
if (j<plen&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')){
i += 1;//检查下一个
j += 1;//"*"匹配任意字符串
}else if (j<plen&&p.charAt(j)=='*'){
istart=i;//记录*匹配的s中的字符串
jstart=j;
j += 1;//j工作指针越过*,到下一个字符
}else if (istart>-1){
istart += 1; //检测到不为*,移动i指针
i=istart;//统计*匹配的字串
j=jstart+1;//统计*匹配的串时,j指针不动
}else {//字符既不相同,也没?*,只有遇到*istart指针位置变
return false; } }//不匹配
//如果匹配完s中的字符,p还剩字符,进一步判断剩下的
//如果都是*,则可以代表空字符,j工作指针往后走
while (j<plen&&p.charAt(j)=='*') j++;
//如果剩下了其它字符,j指针走不到结尾,j<plen
//则需要s中的字符去匹配,但是s已经没有字符匹配,所以false
//如果不剩,则j==plen,完全匹配
return j==plen; }}
Debug结果:
Python题解:
class Solution(object):
def isMatch(self, s, p):
""":type s: str:type p: str:rtype: bool"""
i, j, istart, jstart = 0, 0, -1, -1
slen, plen = len(s), len(p)
if not s or not p: return False #都有可能为空
if not p and not s: return True #都为空为true
#判断s的所有字符是否匹配
while i < slen:
#字符相同或对应了"?"(?匹配任意单个字符)
if j<plen and (s[i]==p[j] or p[j]=='?'):
i += 1 #检查下一个
j += 1
#"*"匹配任意字符串
elif j<plen and p[j]=='*':
istart=i #记录*匹配的s中的字符串
jstart=j
j += 1 #j工作指针越过*,到下一个字符
elif istart > -1:
istart += 1 #检测到不为*,移动i指针
i=istart #统计*匹配的字串
j=jstart+1 #统计*匹配的串时,j指针不动
else: #字符既不相同,也没?*,只有遇到*istart指针位置变
return False #不匹配
#如果匹配完s中的字符,p还剩字符,进一步判断剩下的
#如果都是*,则可以代表空字符,j工作指针往后走
while j<plen and p[j]=='*': j += 1
#如果剩下了其它字符,j指针走不到结尾,j<plen
#则需要s中的字符去匹配,但是s已经没有字符匹配,所以false
#如果不剩,则j==plen,完全匹配
return j==plen
Debug结果:
更多题解移步公众号免费获取