题目内容

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

两个字符串，S作为被匹配的字符串，P作为匹配字符串

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

其中P中有两个特殊元素'?'和'*'，分别可以与任意1个字符匹配和与0-N个字符匹配

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like ? or *.

题目分析以及DP实现思路

举例说明：S='aabcebcd'   P='?*bcd'。首先'？'与'a'匹配，之后*的匹配范围需要我们进行判断，如果以后一个字符即'b'能否与S中的'b'匹配作为依据，那么相当于'*'='a'，但是其后的'cd'并不能与'cebcd'匹配，这时候得出不能匹配的结论显然是不对的，那么要想确定所有的可能我们可以选用动态规划的思路，即：

要确定当前字符是否能达成匹配，首先要考虑上一个字符的匹配状态，以表格为例：

可以看到，常规字符如'?','a-z'能否成功匹配要看是否相同且前段字符串是否匹配（即斜左上角标记）。

而'*'则在上一行（即'*'代表空的情况），前一列（即'*'多匹配一个字符的情况），斜左上角（即之前字符串成功匹配，'*'作为一个字符的情况）三种情况下都可以匹配成功。