192. Wildcard Matching
2019-07-11 本文已影响0人
鸭蛋蛋_8441
Description
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
Example 1
Input:
"aa"
"a"
Output: false
Example 2
Input:
"aa"
"aa"
Output: true
Example 3
Input:
"aaa"
"aa"
Output: false
Example 4
Input:
"aa"
"*"
Output: true
Explanation: '*' can replace any string
Example 5
Input:
"aa"
"a*"
Output: true
Example 6
Input:
"ab"
"?*"
Output: true
Explanation: '?' -> 'a' '*' -> 'b'
Example 7
Input:
"aab"
"c*a*b"
Output: false
思路：
基于记忆化搜索的dfs， 递归的结束条件有点难想，各种情况。
代码：
