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).

 Example
<code>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</code>

Solution1. Dynamic Programming

isMatch[i][j] = if first i chars for s can match first j chars of p

j==’*’: OR(isMatch[0~i][j-1])

j==’?’: isMatch[i-1][j-1]

else: isMatch[i-1][j-1] && s.charAt(i-1)==p.charAt(j-1)

public boolean isMatch(String s, String p) {
    //dp version
    if (s == null || p == null) {
        return false;
    }
    boolean[][] isMatch = new boolean[s.length() + 1][p.length() + 1];
    isMatch[0][0] = true;
    for (int i = 1; i <= s.length(); i++) {
        isMatch[i][0] = false;
    }
    for (int j = 1; j <= p.length(); j++) {
        isMatch[0][j] = isMatch[0][j - 1] && p.charAt(j - 1) == '*';
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') {
                for (int k = 0; k <= i; k++) {
                    if (isMatch[k][j - 1]) {
                        isMatch[i][j] = true;
                        break;
                    }
                }
            } else if (p.charAt(j - 1) == '?') {
                isMatch[i][j] = isMatch[i - 1][j - 1];
            } else {
                isMatch[i][j] = isMatch[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1);
            }
        }
    }
    return isMatch[s.length()][p.length()];
}
FacebookTwitterGoogle+Share

Leave a Reply

Your email address will not be published. Required fields are marked *