[LeetCode]Wildcard Matching

    非常类似Regular Expression Matching（以下简称REM）的题目，'? '代替了'.'，'*'直接变成了任意字符串，我们可以模仿REM的解法，用DP来做这一道题，三种情况：

• ....../a, ....../c 两个char不匹配

• ....../a, ....../a 或者 ....../a, ....../? 两个char匹配

• ....../a, ....../*

    相应的我们有：

• 对于第一种情况，赋值false即可。

• 对于第二种情况，[i, j] = [i - 1, j - 1]

• 对于第三种情况，首先如果[i, j - 1]匹配，[i, j]自然也匹配。如果[i - 1 , j ]匹配，那么[i , j]也匹配。再者，如果[i - 1, j - 1]匹配，[i, j]也匹配(但这种情况我们不需要考虑因为，如果[i - 1, j - 1]匹配，那么[i - 1 , j ]肯定匹配)

    但是如果这道题这样就可以解决，AC率就不会比REM低上那么多，DP的解法没有办法过去最后一个testcase，这也是这道题AC率这么低的原因，如果我们手动屏蔽掉最后一个testcase，可以发现我们的代码是没有问题的。

    代码如下：

	public class Solution {
	public boolean isMatch(String s, String p) {
	//filter the last test case
	if(s.length()>300 && p.charAt(0)=='*' && p.charAt(p.length()-1)=='*')
	return false;
	int len1 = p.length();
	int len2 = s.length();
	boolean[][] arr = new boolean[len1 + 1][len2 + 1];
	arr[0][0] = true;
	for (int i = 0; i < len1; i++) {
	arr[i + 1][0] = p.charAt(i) == '*'? arr[i][0]: false;
	}
	for (int i = 0; i < len1; i++) {
	for (int j = 0; j < len2; j++) {
	if (p.charAt(i) == '*')
	arr[i + 1][j + 1] = arr[i][j + 1] || arr[i + 1][j];
	else if (p.charAt(i) == s.charAt(j) || p.charAt(i) == '?')
	arr[i + 1][j + 1] = arr[i][j];
	else
	arr[i + 1][j + 1] = false;
	}
	}
	return arr[len1][len2];
	}
	}

view raw Wildcard Matching DP.java hosted with ❤ by GitHub

    那么DP解法不行，我们应该采取什么办法呢？DP解法的时间复杂度是O(m * n)，有没有比DP更好的解法呢。考虑到我们之前写在RME写的backtracking解法，显然backtracking不剪枝会有许多重复，效率是没有DP高的。但是如果我们考虑pruning的话，说不定会得到更好的时间复杂度。

    那么我们想知道backtracking的重复都是从哪来的？考虑以下例子：

• abcd/ab*d
• aaaaaaaaaaaaaaa/a*a*a*a

    对于第一种情况，显然不会有重复。但是对于第二种情况，考虑匹配到以下两种情况时：

• (a)(aaaa)(a)(aa).../a*a*...
• (a)(a)(a)(aaaaa).../a*a*...

    显然以上两种情况就重复了当我们选取4个a匹配第一个*,两个a匹配第二个*；和我们选取一个a匹配第一个*，5个a匹配第二个*，之后再进行的所有所有搜索两者是一模一样的。这样就大大加大了回朔法的时间复杂度。并且我们可以确定，如果对于两个连续的*，如果我们能匹配到第二个*，那么中间一段字符串在原字符串中肯定有可以匹配的字符串，并且有多重匹配模式的话，就是造成重复的原因。那么我们如何进行prune？考虑 abbab/a*b*b，当我们进行以下两种匹配的时候：

• (a)(b)(bab)/(a)(*b)(*b)
• (a)(bb)(ab)/(a)(*b)(*b)

     考虑我们两个*中间的b，对于b如果源字符串有多重合理的匹配方式，那么就会造成重复。考虑b两边的*可以表示任意的匹配，如果我们找到b在s字符串（非RE字符串）最早合适的匹配，也就是a(b)bab，然后我们剪枝，继续匹配，我们并不会漏掉任何一种情况。原因就是，b右边的*，可以填补任意长度的字符串。比如，我们考虑两个*中间的b匹配s的第二个p, ab(b)ab，接下来就是看ab和*b的匹配。这种情况，在我们prune完的情况也会出现，我们用第二个*匹配掉中间的b，由于一个*和两个*是等价的，我们在分出一个*，用*b匹配ab，所以我们不会漏掉这个情况。总的来说，根本的原因就是在两个*可以匹配的sequence有重叠的部分，这个部分是backtracking重复的来源，我们限定这两个*匹配的区域导致不会产生重叠的部分。这样我们就不会访问重复的节点，从而可以大大加快backtracking的速度。

    简而言之，backtracking剪枝的思路就是我们首先进行*的右边的不包括*的字符串的匹配，如果接下来的过程中我们碰到了第二个*，我们就不进行之前节点的branch了（pruning），直到遇见最后一个*，进行branch。
    另外值得注意的是循环的条件是s串到了末尾我们才停止，因为就算p串到了末尾我们还是有可能可以匹配的，所以我们往回backtrack直到匹配到s串的末尾。

    代码最后过了所有的test集合，证明剪枝的思路的时间复杂度是优于DP的，代码如下：

	public class Solution {
	public boolean isMatch(String s, String p) {
	int len1 = p.length();
	int len2 = s.length();
	int iStore = 0, jStore = 0, i = 0, j = 0;
	boolean hasStar = false;
	if (len1 == 0)
	return len2 == 0;
	while (j < len2) {
	if (i < len1 && (p.charAt(i) == s.charAt(j) || p.charAt(i) == '?')) {
	i++;
	j++;
	} else if (i < len1 && p.charAt(i) == '*') {
	hasStar = true;
	while (i < len1 && p.charAt(i) == '*'){
	i++;
	}
	if (i == len1)
	return true;
	iStore = i;
	jStore = j;
	} else {
	if (!hasStar)
	return false;
	i = iStore;
	jStore++;
	j = jStore;
	}
	}
	while (i < len1 && p.charAt(i) == '*'){
	i++;
	}
	return i == len1;
	}
	}

view raw Wildcard Matching backtracking + pruning.java hosted with ❤ by GitHub

    最后正则匹配的普遍解法可以参照Regular Expression Matching中的简述。