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).
Have you met this question in a real interview? Yes Example 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 分析:Hulu面试时遇到过类似的正则表达式匹配题目，比这道题稍难，除了 '?' , '*', 应该还有'.'二维动态规划。res[i][j]代表s第0～i个字符是否和p第0～j个字符匹配。注意初始时考虑s，p首字符为*的情况。
遇到问号时，res[i][j] = res[i - 1][j - 1] 遇到星号时，res[i][j] = res[i - 1][k] k from 1 to j - 1.假设星号在s上。即s字符串除去星号后的0～星号前一位组成的字符串，去和p字符串j位置之前的所有字符串匹配，如果有匹配成功的，那么说明星号可以代替两个字符串之间相差的字符串。 那么res[i][j] = true. 本来考虑k的范围从i - 1到j-1,但是这种情况忽略了星号前边还有星号的情况。所以需要从1开始。或者引入临时变量，记录有效字符的数量，然后从这个数字开始执行for。
public class Solution { /** * @param s: A string * @param p: A string includes "?" and "*" * @return: A boolean */ public boolean isMatch(String s, String p) { boolean[][] res = new boolean[s.length() + 1][p.length() + 1]; res[0][0] = true; if(s.length() != 0 && s.charAt(0) == '*') { for(int i = 0; i <= p.length(); i++) { res[1][i] = true; } } if(p.length() != 0 && p.charAt(0) == '*') { for(int i = 0; i <= s.length(); i++) { res[i][1] = true; } } for(int i = 1; i <= s.length(); i++) { for(int j = 1; j <= p.length(); j++) { if((s.charAt(i - 1) == p.charAt(j - 1)) || (s.charAt(i - 1) == '?') || (p.charAt(j - 1) == '?')) { res[i][j] = res[i - 1][j - 1]; } else if(s.charAt(i - 1) == '*') { for(int k = 1; k <= j; k++) { if(res[i - 1][k]) { res[i][j] = true; break; } } } else if(p.charAt(j - 1) == '*') { for(int k = 1; k <= i; k++) { if(res[k][j - 1]) { res[i][j] = true; break; } } } else { res[i][j] = false; } } } return res[s.length()][p.length()]; } }
