首页 > 代码库 > [leetcode] Wildcard Matching
[leetcode] Wildcard Matching
题目：（DP，BackTracking， Greedy，String）
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 express 那题很像，但是有区别。
首先要用贪心算法，就是两个string，一个char一个char的对比下去，
然后这题主要要分析的地方就是当*出现的时候，这时候要做的是s继续往后挪，看看能不能跟*后面的元素匹配上，能匹配上就继续往后对比。
public class Solution { public boolean isMatch(String s, String p) { int i=0; int j=0; int start=-1; int mark=-1; while(i<s.length()) { if(j<p.length()&& (s.charAt(i)==p.charAt(j)||p.charAt(j)==‘?‘)) { ++i; ++j; } else if(j<p.length()&&p.charAt(j)==‘*‘) { start=j++; mark=i; } else if(start!=-1) { j=start+1; i=++mark; } else { return false; } } while(j<p.length()&&p.charAt(j)==‘*‘) j++; return j==p.length(); }}
[leetcode] Wildcard Matching
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。