首页 > 代码库 > Leetcode-Wildcard Matching
Leetcode-Wildcard Matching
‘?‘ Matches any single character.‘*‘ Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false
Analysis:
1. DP solution:
d[i][j]: whether first j chars of s cannot matched by the first i chars of p.
State transition formula:
if p[i]==‘*‘: if there exists some k<=j so that d[i-1][k] is true, then d[i][j] is true;
if p[i]==‘?‘: if d[i-1][j-1] is true, then d[i][j] is true;
if p[i]==some char: if p[i]==s[i] && d[i-1][j-1], then d[i][j] is true;
NOTE:
for the case that p[i]==‘*‘, for d[i-1][j], if the first true appears at some k (d[i-1][k]), then d[i][k] to d[i][j] are all true. Using the property can reduce some complexity.
HOWEVER:
The complexity is too high to meet the time constraint on Leetcode.
2. Backtracking:
We can use two pointers pInd and sInd to record the current matched place of p and s.
if p[pInd]==s[sInd] || p[pInd]==‘?", then this place is matched, we move to next place: pInd++ and sInd++;
if p[pInd]==‘*‘, then we record its place as star and record sInd as starS, and increase pInd.
if at some step, we cannot match pInd and sInd, we then backtrack to the last place of ‘*‘, i.e., star, and starS++ and sInd=starS.
In this way, we actually increase the substring that is matched by the last ‘*‘ by 1 more char, and start to match the rest of strings again.
NOTE:
The essence here is to change the substring matched by a ‘*‘. We start from macth ‘*" with an empty substring in s. If we cannot match the rest of s, we then let the last ‘*‘ to match one more char, and try again.
Solution:1 public class Solution { 2 public boolean isMatch(String s, String p) { 3 int sLen = s.length(); 4 int pLen = p.length(); 5 if (s=="" && p=="") return true; 6 7 8 int pInd = 0; 9 int sInd = 0;10 int star = -1;11 int starS = -1;12 char charS, charP;13 while (true){14 //Determin the current state of the problem first.15 //if all s has been matched, but there is still unused p, 16 //then return true only if all the p left are ‘*", otherwise return false;17 if (pInd<pLen && sInd>=sLen){18 for (int i=pInd;i<pLen;i++)19 if (p.charAt(i)!=‘*‘)20 return false;21 return true;22 }23 24 //If all the p has been used25 if (pInd>=pLen){26 //if still has unmatched s, then backtrack to the last currence of ‘*‘27 //otherwise, return true;28 if (sInd<sLen){29 if (star==-1) return false;30 pInd = star+1;31 starS++;32 sInd = starS;33 } else return true;34 } else {35 charS = s.charAt(sInd);36 charP = p.charAt(pInd);37 boolean match = false;38 if (charP==‘?‘ || charP==charS){39 pInd++; 40 sInd++;41 } else if (charP==‘*‘){42 star = pInd;43 starS = sInd;44 pInd++;45 } else {46 if (star==-1) return false;47 pInd = star+1;48 starS++;49 sInd = starS;50 }51 }52 }53 }54 }
Leetcode-Wildcard Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。