Wildcard Matching
This is the solution about Leetcode  44.Wildcard Matching.
Description
Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.


The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters az.
p could be empty and contains only lowercase letters az, and characters like ? or *.
Example 1:


Example 2:


Example 3:


Example 4:


Example 5:


Solution
Solution1
 Recursion: This solution is Time Limit Exceeded
 Each time we compare with the first letter of s and p. And recursively compare with the rest of s and p.
 if ‘*’ is present, it has three situations:
 star represents multiple letters > compare s.substring(1) and p;
 star represents one letter > compare s.substring(1) and p.substring(1);
 star represents none letter > compare s and p.substring(1);
Solution2
 DP solution.
 Record first i and first j letters of s and p are matched or not into array. From (0,0) to (s.length(), p.length()) to get the result of s and p.
 Similar thinking of recursive solution. if ‘*’ is present, it has three situations:
 ‘*’ represents multiple letters > j should match i1 as well > dp[i+1][j+1] = dp[i][j+1]
 ‘*’ represents one letter > i1 and j1 are matched > dp[i+1][j+1] = dp[i][j]
 ‘*’ represents none letter > i and j1 are matched > dp[i+1][j+1] = dp[i+1][j]

