Created
May 9, 2013 20:38
-
-
Save daifu/5550430 to your computer and use it in GitHub Desktop.
Wildcard Matching
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Work on process........... | |
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") ? false | |
isMatch("aa","aa") ? true | |
isMatch("aaa","aa") ? false | |
isMatch("aa", "*") ? true | |
isMatch("aa", "a*") ? true | |
isMatch("ab", "?*") ? true | |
isMatch("aab", "c*a*b") ? false | |
*/ | |
public class Solution { | |
public boolean isMatch(String s, String p) { | |
// Start typing your Java solution below | |
// DO NOT write main() function | |
if(s.length() == 0 && p.length() == 0) return true; | |
if(s.length() == 0 && p.charAt(0) == '*') return true; | |
return isMatchHelper(s, 0, p, 0); | |
} | |
public boolean isMatchHelper(String s, int ss, String p, int ps) { | |
if(ss == s.length() && ps == p.length()) return true; | |
if(ss == s.length()) { | |
while(ps < p.length() && p.charAt(ps) == '*') { | |
ps++; | |
} | |
if(ps != p.length()) return false; | |
else return true; | |
} | |
if(ps == s.length()) return false; | |
if(p.charAt(ps) == '?') | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment