• 解题:通配符表达式[难度难]

    2015/10/31 JSRGFJZ

题目:

给出两个字符串,有如下配对准则:
‘.’ 配对任意字符.
‘*’ 可以和之前的一个字符配对多次,包括0次。

示例:

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

思路:

第一个思路:动态规划

f[i][j]== s[0…i-1] p[0…j-1] 是否配对。

f[i+1][j+1]的配对由前面的几个配对:p[j]是不是“*”,

不是的话,很简单,只需要看p[j-1]==s[i-1]||p[j-1]==’.’

如果是,这个时候,就要把前面的那个字符重复使用了,如果使用0次,就看f[i+1][j-1],如果使用1次,就看f[i][j-1]&&p[j-1]==”.”||p[j-1]=s[i]

以此类推。

第二个思路:迭代

首先判断下下个字符是不是*,如果不是,很简单,判断两者是否相等,或者p[j-1]==’.’,弹药注意s没有到尾部。

如果是的呢,首先递归调用自己,判断(isMatch(s, p.substr(2))),这个时候其实就是使用前面字符0次

接下来就是使用1次,2次等等….只不过与动态规划不一样的是,他是往后走,这也更容易理解。这部分见代码很容易理解。

代码:

 

1 收藏


直接登录