Problem:
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
Reference: http://shmilyaw-hotmail-com.iteye.com/blog/2154716
Method 1: Greedy
str: the original string we need to examine
pattern: the string with wildcard
s: the cursor in str
p: the cursor in p
StarIdx: the place of the last encountered * (Initialize as -1)
match: the place in str, when p encountered a *
- We go through every char in str
- If p and s match, p++, s++
- If p and s do not match, and p encounter a *: remember the current place of p and s in ‘StarIdx’ and ‘match’. Then, p++l .
- If p and s do not match, and p does not encounter a *, but StarIdx is not -1: update p as StarIdx+1, update match as match+1, update s as match.
- If p and s do not match, and p does not currently at a *, and p does not ever encountered an * before, we can decide, the two string do not match. Return false;
- After checking every char in str, we need to check if there are still char left in p. We only allow *.
Code:
public class Solution { public boolean isMatch(String str, String pattern) { int s = 0; // cursor for traversal in str. int p = 0; // cursor for traversal in pattern. int starIdx = -1; // once we found a star, we want to record the place of the star. int match = 0; // once we found a star, we want to start to match the rest of pattern with str, starting from match; this is for remembering the place where we need to start. // we check and match every char for str. while (s < str.length()){ // 1. case 1: we are not currently at any *, if (p < pattern.length() && (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '?')){ p++; s++; }// 2. case 2: we are currently at a '*' else if (p < pattern.length() && pattern.charAt(p) == '*' ){ starIdx = p; p++; match = s; } // 3. case 3: they do not match, we do not currently at a *, but the last matched is a * else if (starIdx != -1){ match++; s = match; p = starIdx + 1; } // 4. case 4: they do not match, do not currently at a *, and last matched is not a *, then the answer is false; else{ return false; } } // when we finish matching all characters in str, is pattern also finished? we could only allow '*' at the rest of pattern while (p < pattern.length() && pattern.charAt(p) == '*') p++; return p == pattern.length(); } }
Method 2:
We could use recursive method. Recursive: we just check one step. Iterative: we use while to check all steps.
- Parameters:
- String str: the original string
- String pattern: the pattern string
- int l: the cursor in original string
- int r: the cursor in pattern string
- Function: starting from l and r, the left part do match.
- Base Case: If r reaches the end of str, we need to check if l also reaches the end of pattern. If so, match.
- Reduction: check the current char in pattern string
- If regular, just increase l and r by 1;
- If *, first, go to the last *, and then check if match. (we have to use while loop to find the correct starting point.)
Code for method 2:
public class Solution { public boolean isMatch(String s, String p) { return helper(s,p,0,0); } boolean helper(String s, String p, int l, int r) { if(r == p.length()) return l == s.length(); if(p.charAt(r) == '*') { while(r < p.length() && p.charAt(r) == '*') r++; // Move the index at p to a non-start char. while(l < s.length()) { if(helper(s, p, l, r)) return true; // Find one match, return true. l++; // Try the next one. } return helper(s, p, l, r); }else if(l < s.length() && (p.charAt(r) == '?' || s.charAt(l) == p.charAt(r))){ return helper(s, p, l + 1, r + 1); }else{ return false; } } }
Method 3:
However, the recursive method is too slow and we need to have a quicker speed. So we try to solve it by DP.
1. Regular case: if two chars are the same, or p is ‘?’, then go to check dp[i-1][j-1]
2. Special case: when p is ‘*’, we need to check dp[i-1][j-1] for every i>0. If there is one true, then the answer is true.
Code for method 3:
// use DP public class Solution { public boolean isMatch(String s, String p) { int width = s.length(); int height = p.length(); boolean[][] dp = new boolean[width + 1][height + 1]; dp[0][0] = true; for (int i = 1; i <= width; i++){ for (int j = 1; j <= height; j++){ if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){ dp[i][j] = dp[i-1][j-1]; }else if (p.charAt(j-1) == '*'){ int cur = i; while (cur > 0){ if (dp[cur-1][j-1]){ dp[i][j]= true; break; } cur--; } } } } return dp[width][height]; } }