LeetCode程序员面试金典：通配符匹配

　　题目：

　　给你一个输入字符串 (s) 还有一个字符模式 (p) ，请实现一个支持性的通配符，与“*”匹配规则相匹配：

　　任何单个字符都可以匹配。

　　任何字符序列(包括空字符序列)都可以匹配。

　　成功匹配的充电条件是：字符模式必须能够完全匹配输入字符串(而不是部分匹配)。

　　示例 1：输入：s = "aa", p = "a“输出：false解释：”a" 无法匹配 "aa" 整个字符串。

　　示例 2： 输入：s = "aa", p = "*"输出:true解释:"* 任何字符串都可以匹配。

　　示例 3： 输入：s = "cb", p = "?a"输出:false解释:" 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

　　代码实现： class Solution { public boolean isMatch(String s, String p) { int m = s.length(); int n = p.length(); boolean[][] dp = new boolean[m + 1][n + 1]; dp[0][0] = true; for (int i = 1; i <= n; ++i) { if (p.charAt(i - 1) == '*') { dp[0][i] = true; } else { break; } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (p.charAt(j - 1) == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } } } return dp[m][n]; }}