解法一 动态规划
直接按照之前第 10 题，修改一下就可以了。
同样是用 dp[i][j] 表示所有的情况，然后一层一层的根据递推关系求出来。
publicbooleanisMatch(Stringtext, Stringpattern) { // 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了boolean[][] dp=newboolean[text.length() +1][pattern.length() +1]; // dp[len][len] 代表两个空串是否匹配了，"" 和 "" ，当然是 true 了。dp[text.length()][pattern.length()] =true; // 从 len 开始减少for (inti=text.length(); i>=0; i--) { for (intj=pattern.length(); j>=0; j--) { // dp[text.length()][pattern.length()] 已经进行了初始化if (i==text.length() &&j==pattern.length()) continue; //相比之前增加了判断是否等于 * booleanfirst_match= (i<text.length() &&j<pattern.length() && (pattern.charAt(j) ==text.charAt(i) ||pattern.charAt(j) =='?'||pattern.charAt(j) =='*')); if (j<pattern.length() &&pattern.charAt(j) =='*') { //将 * 跳过 和将字符匹配一个并且 pattern 不变两种情况dp[i][j] =dp[i][j+1] ||first_match&&dp[i+1][j]; } else { dp[i][j] =first_match&&dp[i+1][j+1]; } } } returndp[0][0]; }
时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O（TP）。
空间复杂度：O（TP）。
同样的，和第10题一样，可以优化空间复杂度。
publicbooleanisMatch(Stringtext, Stringpattern) { // 多一维的空间，因为求 dp[len - 1][j] 的时候需要知道 dp[len][j] 的情况，// 多一维的话，就可以把 对 dp[len - 1][j] 也写进循环了boolean[][] dp=newboolean[2][pattern.length() +1]; dp[text.length() %2][pattern.length()] =true; // 从 len 开始减少for (inti=text.length(); i>=0; i--) { for (intj=pattern.length(); j>=0; j--) { if (i==text.length() &&j==pattern.length()) continue; booleanfirst_match= (i<text.length() &&j<pattern.length() && (pattern.charAt(j) ==text.charAt(i) ||pattern.charAt(j) =='?'||pattern.charAt(j) =='*')); if (j<pattern.length() &&pattern.charAt(j) =='*') { dp[i%2][j] =dp[i%2][j+1] ||first_match&&dp[(i+1) %2][j]; } else { dp[i%2][j] =first_match&&dp[(i+1) %2][j+1]; } } } returndp[0][0]; }
时间复杂度：text 长度是 T，pattern 长度是 P，那么就是 O（TP）。
空间复杂度：O（P）。
总
动态规划的应用，理清递推的公式就可以。另外迭代的方法，也让人眼前一亮。
