首页 > 代码库 > 【leetcode】Wildcard Matching
【leetcode】Wildcard Matching
Wildcard Matching
Implement wildcard pattern matching with support for ‘?‘ and ‘*‘.
‘?‘ 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类似于Regular Expression Matching，会超时
1 class Solution { 2 public: 3 bool isMatch(const char *s, const char *p) { 4 5 if(*s==‘\0‘&&*p==‘\0‘) return true; 6 if(*s!=‘\0‘&&*p==‘\0‘) return false; 7 if(*s==‘\0‘&&*p!=‘\0‘) return false; 8 9 if(*p==‘*‘)10 {11 while(*p==‘*‘) p++;12 13 14 while(*s!=‘\0‘)15 {16 if(isMatch(s,p)) return true;17 s++;18 }19 20 return isMatch(s,p);21 }22 else if(*p==‘?‘)23 {24 return isMatch(s+1,p+1);25 }26 else27 {28 return (*s==*p&&isMatch(s+1,p+1));29 }30 31 32 return false;33 }34 };
采用类似回溯的思想
依次对字符进行比对，如果发现p==‘*‘
则从（p+1）开始和s开始依次比较，如果发现不对，
则回溯到（p+1）的位置，再从s+1开始依次比较
如果再不对，则再次回溯到(p+1)的位置，从s+2位置开始依次比较
……
1 class Solution { 2 public: 3 bool isMatch(const char *s, const char *p) { 4 5 6 const char* afterStarPositionP=NULL; 7 const char* afterStarPositionS=NULL; 8 while(*s!=‘\0‘) 9 {10 if(*s==*p||*p==‘?‘)11 {12 s++;p++;13 continue;14 }15 else if(*p==‘*‘)16 {17 p++;18 afterStarPositionP=p;19 afterStarPositionS=s;20 }21 else22 {23 if(afterStarPositionP!=NULL)24 {25 afterStarPositionS++;26 s=afterStarPositionS;27 p=afterStarPositionP;28 }29 else30 {31 return false;32 }33 }34 }35 36 while(*p==‘*‘)37 {38 p++;39 }40 41 if(*p==‘\0‘) return true;42 else return false;43 }44 };
【leetcode】Wildcard Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。