Skip to content

Instantly share code, notes, and snippets.

@wayetan
Created March 6, 2014 21:16
Show Gist options
  • Save wayetan/9399796 to your computer and use it in GitHub Desktop.
Save wayetan/9399796 to your computer and use it in GitHub Desktop.
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") → 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) {
int len_s = s.length();
int len_p = p.length();
if(len_s == 0 && len_p == 0)
return true;
int i = 0, j = 0;
// save the last matched index
int start_s = -1, start_p = -1;
while (i < len_s) {
if (j < len_p && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
i++;
j++;
} else if (j < len_p && p.charAt(j) == '*') {
while(j < len_p && p.charAt(j) == '*')
j++;
if(j == len_p)
return true;
// 置上一个开始比较的位置
start_p = j;
start_s = i;
} else if ((j >= len_p || s.charAt(i) != p.charAt(j)) && start_p > -1) {
start_s++;
// 恢复到上一次比较的下一个位置
j = start_p;
i = start_s;
} else {
return false;
}
}
while (j < len_p) {
if (p.charAt(j) != '*')
return false;
j++;
}
return true;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment