Wildcard Matching
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
public class Solution {
public boolean isMatch(String s, String p) {
boolean[][] match=new boolean[s.length()+1][p.length()+1];
match[s.length()][p.length()]=true;
for(int i=p.length()-1;i>=0;i--){
if(p.charAt(i)!='*')
break;
else
match[s.length()][i]=true;
}
for(int i=s.length()-1;i>=0;i--){
for(int j=p.length()-1;j>=0;j--){
if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')
match[i][j]=match[i+1][j+1];
else if(p.charAt(j)=='*')
match[i][j]=match[i+1][j]||match[i][j+1];
else
match[i][j]=false;
}
}
return match[0][0];
}
}
Related Problems
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.
If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.
Return the maximum coins you can collect by bursting the balloons wisely.
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.
Given two strings s and t, return the number of distinct subsequences of s which equals t.