# My easy java solution using dynamic programing

• ``````/*
* Assumptions:
* Assume that bother input and pattern are not null.
*
* Steps: Fill out a 2D boolean array to find if there exists a matching wildcard. array[i][j] repqresents if
*        there exist a wildcard matching from first element of input and pattern to ith element of input and jth element
*        from pattern.
*
* Induction rules: if(p.charAt(i - 1) == s.charAt(j - 1) || p.charAt(i - 1) == '?'), then
* 						ifMatched[j][i] = ifMatched[j][i] || ifMatched[j- 1][i - 1];
* 					else if(p.charAt(i - 1) == '*'), then
* 						ifMatched[j][i] = ifMatched[j - 1][i] || ifMatched[j][i - 1];
*
* return array[input.length][pattern.length].
*
* Time Complexity:o(n*m)  Space Complexity:o(n*m)
*/

public boolean isMatch(String s, String p) {
boolean[][] ifMatched = new boolean[1 + s.length()][1 + p.length()];
ifMatched[0][0] = true;
for(int i = 1; i <= p.length(); i++){
if(p.charAt(i - 1) != '*'){
break;
}
ifMatched[0][i] = true;
}
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= p.length(); j++){
if(p.charAt(j - 1) == '*'){
ifMatched[i][j] = ifMatched[i - 1][j] || ifMatched[i][j - 1];
} else if(p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?'){
ifMatched[i][j] = ifMatched[i - 1][j - 1];
}
}
}
return ifMatched[s.length()][p.length()];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.