44. Wildcard Matching - YRB - 博客园

44. Wildcard Matching - YRB - 博客园

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).  The matching should cover the entire input string (not partial).  The function prototype should be: bool isMatch(const char *s, const char *p)  Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "*") → true isMatch("aa", "a*") → true isMatch("ab", "?*") → true isMatch("aab", "c*a*b") → false

链接：  http://leetcode.com/problems/wildcard-matching/

题解：

这道题是一刷里放弃的6道题中第一道。看过<挑战程序设计>以后还是决定好好对待这道题目。 前些天专门学习了NFA，但对这道题目还是会time out。试过把*预处理为"?*"之后可以用regular expression的DP方法来过，但是速度比较慢。 这道题也是Two Sigma上午三轮技术面里必考的一道题。 以后再遇到这类题目，我要尽可能使用DP来做，好好练习DP。

又做到了这一题，下面用dp来解决。虽然AC但是速度很慢，有很多地方需要优化，比如更多的pruning，Space Complexity减少为O(n)等等。Reference里有三个解得就非常好。 留给三刷继续深入研究这道题目。

下面使用DP解决的思路。代码大部分和 10. Regular Expression Matching 一样。直接拷贝自己的解释。

使用DP的方法: 

1. 在初始的判断之后，首先建立dp矩阵res[][] = new boolean[m + 1][n + 1]。其中res[i][j]是指s到字符i - 1，p到字符j - 1的match情况，true为match。
2. res[0][0] = true表示s和p都为""的时候match成功
3. 接下来对pattern p的首行'*'号的0 match情况进行初始化，res[0][j] = res[0][j - 1] && p.charAt(j - 1) == '*'。这里表示，假如res[0][j - 1]，也就是""与p.charAt(j - 2)成功match，那么因为当前字符p.charAt(j - 1) = '*'可以代表空字符串，所以res[0][j]也肯定match成功。我们发现在10. Regular Expression Matching与这一题44. Wildcard Matching中， 合理得初始化都是都是必不可少的步骤。
4. 之后我们就可以从从位置(1, 1)开始对res矩阵进行二维dp，主要分为两种情况
1. p.charAt(i - 1)不等于'*'： 这里表示matching transition，假如s和p的上一个字符match, 即res[i - 1][j - 1] == true，同时新的字符s.charAt(i - 1) == p.charAt(j - 1)，或者p.charAt(j - 1) == '?'， 那么我们可以确定res[i][j] = true，这表示到 s 和 p 到 i - 1和j - 1的位置是match的
2. 假如p.charAt(i - 1) == '*': 这里表示epsilon transition，系统可能处于不同的状态，我们要分多种情况进行考虑，只要有一个状态为true，在这个位置的结果就为true，是一个"或"的关系:
1. res[i][j - 1] == true，即s.charAt(i - 1) match p.charAt(j - 2)，这里'*'号可以当作""，表示0 matching，这种情况下，我们可以认为状态合理，res[i][j] = true。 例 "C" match "C*"， i = 2， j = 2，这里C match C，'*'作为空字符串""，所以我们match成功
2. res[i - 1][j] == true，即s.charAt(i - 2) match p.charAt(j - 1)，这里'*'号是被当做"s[j - 2]" + "s[j - 1]"这两个字符拼起来的字符串。因为'*'可以代表任意字符串，所以假如res[i - 1][j] == true，那么res[i][j]也一定是true，其实这样类推下去，res[i + 1][j]也是true，这一列都是true。 (根据这个特性其实我们可以巧妙地改写一下，提前把这一列剩下元素都设置为true，可以减少不少数组访问)。 例 "AC" match "*", i = 2, j = 1，这时候'*'可以作为'AC'，所以也是match成功。
5. 数组全部遍历完毕之后我们返回res[m][n] 

Read full article from 44. Wildcard Matching - YRB - 博客园