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()]; }