LeetCode 10 Regular Expression Match

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

对于我这种算法菜鸟都不算的门外汉，自然写出了又长又臭的if else考虑了一大堆的case，结果还是各种bug各种case通不过。。。醉了，早好好学习也不至于现在这么狼狈，还好不是太晚。

最终参考了http://blog.csdn.net/hopeztm/article/details/7992253浙大牛人的思路加代码

这题主要运用动态规划（DP）：（这里用s指向源串，p指向待匹配串）

跟上题回文匹配类似使用dp[i][j]表示s[0...strlen(s)]和p[0...strlen(p)]的匹配情况

if *(p+1) != '*'

if *p == *s dp[i][j] = dp[i+1][j+1]

　　else return false

if *(p+1) == '*' 这是需要考虑拓展.*的情况来匹配，并且每一步都要增加s，如果匹配返回true，否则返回通配符匹配后的结果。

这里面由dp[i][j]到dp[i+1][j+1]就是迭代的过程，后面每次增加s检查匹配也是迭代，若增加s的过程无匹配，则退回到最开始通配符匹配环节。

巴特西

LeetCode 10 Regular Expression Match

最新文章

热门文章