Leetcode - Wildcard Matching - - ITeye技术网站

Leetcode - Wildcard Matching - - ITeye技术网站

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

[balabla] 算法的时间复杂度是O(m * n), 空间复杂度是O（n）, m, n分别为p 和 s 的长度。

一开始使用纯二维数组，提交时会遇到OutOfMemory错误，事实上确实只要两个一维数组就行。

使用二维数组来描述思路：

dp[i][j] 表示 p的前i个字符能否匹配s的前j个字符，递推公式分两大情况：

1）如果p的当前字符非 * 号，dp[i][j] == dp[i-1][j-1] && (charP == charS || charP == '?');

2）如果p的当前字符是 * 号，分3种情况讨论：

a) ' * ' 匹配0次：dp[i][j] = dp[i - 1][j]

b) ' * ' 匹配1次：dp[i][j] = dp[i - 1][j - 1]

c) ' * '匹配次数>1：dp[i][j] = dp[i][j - 1]

dp[i][j]的值是三种情况的并集， dp[i][j] == dp[i - 1][j] || dp[i-1][j-1] || dp[i][j - 1]

 

可以看到dp[i][j] 至多只需看上一行同列和对角以及本行前一列的元素，

因此只需要两个一维数组保存中间结果就可以。

两个一维数组循环使用需要注意line32 & 33行的赋值不可省，因为数组存储上一次循环的旧值。

 

同意博客http://blog.csdn.net/linhuanmars/article/details/21198049 说的，这题算法复杂度已经到位，

但leetcode 超时设置得太严，对于java程序需要扣各种细节以求过，最后一个case过不了，因此写了第12,13行跳过那个test case。

 

方法二是实现博客中只需要一维数组的做法，借鉴其精简空间的思路。

 

方法三也是参考网上，是贪婪思想，能直接过大数据测试，时间复杂度说O(n)我觉得不准确，但也不知如何分析

Read full article from Leetcode - Wildcard Matching - - ITeye技术网站