44. Wildcard Matching
这道题和10. Regular Expression Matching很像，基本思想是一样的，都是二维DP，但本题又会有些特殊的地方。
- 状态定义：
dp[i][j]==1表示s的前i个字符和p的前j个字符能匹配上 - 初始状态：
dp[0][0]==0；dp[i][0]全是0；if(char[j-1]=='*' && dp[0][j-1]==1) dp[0][j]=1 else dp[0][j]=0；初始状态这里要仔细想想，如果p要匹配一个空字符串，必须要当前字符（假设当前字符下标是j）是*，并且p.substring(0,j-1)也能匹配空字符串。 - 状态转移方程：
- 如果当前字符是
*，那么p.substring(0,j-1)只要能匹配s的任意字串就可以了，剩余的部分由*去匹配 - 如果当前字符是
?，必须有p.substring(0,j-1)和s.substring(0,i-1)能匹配上，s和p才能匹配上 - 如果当前字符是其他字符，必须有
p.substring(0,j-1)和s.substring(0,i-1)能匹配上，并且s.charAt(i)==p.charAt(j)，s和p才能匹配上
- 如果当前字符是
状态转移方程看着复杂，但仔细想想就能理解的。相比之前的正则匹配，已经简单很多了。
根据这个思路，有了第一个解法：
public class Solution {
public boolean isMatch(String s, String p) {
// s的前i个字符和p的前j个字符能匹配上
int[][] dp = new int[s.length() + 1][p.length() + 1];
dp[0][0] = 1;
// dp数组中，有哪些列存在值为1的元素？后面会用到
Set<Integer> colSet = new HashSet<Integer>();
// 初始状态
for (int i = 1; i < p.length() + 1; i++) {
char thisChar = p.charAt(i - 1);
if (thisChar == '*' && dp[0][i - 1] == 1) {
dp[0][i] = 1;
colSet.add(i); // 别忘了更新colSet
}
}
// 开始计算dp数组，注意i和j的初始值
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < p.length() + 1; j++) {
if (p.charAt(j - 1) == '*') {
if (colSet.contains(j - 1))
dp[i][j] = 1;
} else if (p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1] == 1 ? 1 : 0;
} else {
dp[i][j] = dp[i - 1][j - 1] == 1 && s.charAt(i - 1) == p.charAt(j - 1) ? 1 : 0;
}
if (dp[i][j] == 1)
colSet.add(j);
}
}
return dp[s.length()][p.length()] == 1;
}
}
代码还是挺简单的，这个思路应该也是对的。但对于一些corner case这个解法会MLE。。。话说这是我第一次在leetcode上看到MLE。。。一般我们都会更关注时间复杂度，空间限制上考虑的很少。
MLE的case中，p是8000多个a加一个*组成的，按我的解法，dp数组会非常大，大概就是dp[100][10000]的规模，于是超出了空间限制。那有没有什么办法可以优化空间使用呢？
首先想到的就是简化下p，参考正则表达式的写法，比如aaaaaaaaaaaa如果写成正则，可以写成a[12]，明显长度会小很多。简化长度后再用DP去算，就不会MLE了。优化后的解法：
public class Solution {
public boolean isMatch(String s, String p) {
// 第一步：精简pattern
StringBuilder sb = new StringBuilder(); // 存储简化后的pattern
Map<Integer, Integer> pCount = new HashMap<Integer, Integer>(); // 存储简化后pattern每个字符的出现次数
// 比如原始pattern是aaaaaaaa***，简化后就是a*
// 其中a出现8次，*出现2次，对应map中的元素就是0->8，1->2
// pCount这个map的作用就类似与正则中的中括号：a[2-5]
char lastChar = 0;
int lastCount = 0, currentIndex = 0;
for (int i = 0; i < p.length(); i++) {
char thisChar = p.charAt(i);
if (lastCount == 0) {
lastCount = 1;
lastChar = thisChar;
continue;
}
if (lastChar != thisChar) {
pCount.put(currentIndex, lastCount);
sb.append(lastChar);
currentIndex++;
lastCount = 1;
lastChar = thisChar;
} else {
lastCount++;
}
}
if (lastCount != 0) {
pCount.put(currentIndex, lastCount);
sb.append(lastChar);
}
//System.out.println(pCount);
//System.out.println(sb.toString());
// 第二步，简化完毕，开始DP，状态定义和初始状态都和以前一样
// 但注意状态转移方程的变化
p = sb.toString();
// s的前i个字符和p的前j个字符能匹配上
int[][] dp = new int[s.length() + 1][p.length() + 1];
dp[0][0] = 1;
// dp数组中，有哪些列存在值为1的元素？后面会用到
Set<Integer> colSet = new HashSet<Integer>();
colSet.add(0);
// 初始状态
for (int i = 1; i < p.length() + 1; i++) {
char thisChar = p.charAt(i - 1);
if (thisChar == '*' && dp[0][i - 1] == 1) {
dp[0][i] = 1;
colSet.add(i);
}
}
// 计算dp矩阵
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 1; j < p.length() + 1; j++) {
// 对于*不用考虑pCount，因为多个*连续出现和单独一个*效果是一样的
if (p.charAt(j - 1) == '*') {
if (colSet.contains(j - 1))
dp[i][j] = 1;
}
// 如果是多个连续的?，比如xxxabc要匹配yyy???，只要xxx能匹配上yyy就可以了
else if (p.charAt(j - 1) == '?') {
dp[i][j] = i - pCount.get(j - 1) >= 0 && dp[i - pCount.get(j - 1)][j - 1] == 1 ? 1 : 0;
}
// 如果当前字符是个普通字符，稍微复杂
else {
boolean flag = true;
char thisChar = p.charAt(j - 1);
// 必须同时满足2个条件：
// 1. s的结尾必须是连续pCount个thisChar
// 2. s去除结尾的pCount个字符后，剩下的字符串能和p.substring(0,j-1)匹配上
if (i - pCount.get(j - 1) >= 0 && dp[i - pCount.get(j - 1)][j - 1] == 1) {
for (int k = i - 1; k >= i - pCount.get(j - 1); k--) {
if (thisChar != s.charAt(k)) {
flag = false;
break;
}
}
} else {
flag = false;
}
if (flag)
dp[i][j] = 1;
}
if (dp[i][j] == 1)
colSet.add(j);
}
}
return dp[s.length()][p.length()] == 1;
}
}
这个解法能够AC了，但感觉还是有点慢。。。应该还有可以优化的地方。
而且那个colSet似乎有些多余。。。