Leetcode Wildcard Matching 解题报告

1 解题思想

近期在处理Hard难度的题目时频率明显增加，而当前的注意力重心已不再集中于Leetcode平台，这种状态确实让人感到疲惫。Hard级别的题目在处理过程中总是显得格外繁琐。

这道题似乎之前也有过类似的讨论，主要涉及的是通配符的匹配问题，其中*可以匹配任意长度的字符，？则能匹配任意单个字符，现在需要判断给定的通配符是否能够与输入字符串成功匹配。

对于这道题而言，存在多种解题思路，而我所采用的方法仅属于较为常规的一种。由于该题的数据规模较大，简单的暴力搜索方式难以通过所有测试用例。因此我选择使用动态规划的方式来解决这一问题。

是否有人了解过LCS（最长公共子序列）这类算法呢？我的思路正是基于LCS的相关原理来构建动态规划模型。

定义一个二维矩阵[,]用于表示当前已匹配的通配符长度
初始状态下[0,0]的位置为true，即当输入字符串和通配符均为空时视为匹配成功；其余位置初始值为false
假设当前比较的是输入字符串中的第i个字符与通配符中的第j个字符，在[i,j]这个位置上：
1、如果当前通配符是*号，则当前位置能否匹配取决于其左侧、上方或左上方是否有至少一个位置是可以到达的
2、如果当前通配符是？或者与输入字符串中的对应字符相等，则当前位置能否匹配取决于左上方[i-1,j-1]的位置是否可达
若上述两种情况均不满足，则说明第i个字