非死不可店面跪经

写了一个o(n^2)的解法供讨论，楼主面试可能太紧张了吧，效果会适得其反。
isMatch(String s1, String s2) {
        if(s2.isEmpty()) return s1.isEmpty();
        char[] chs1 = s1.toCharArray();
        char[] chs2 = s2.toCharArray();
        int m = chs2.length, n = chs1.length;
        int[][] dp = new int[m+1][n+1];
        for(int i=0;i<=n;++i) dp[0][i] = true;
        dp[0][0] = true;
        for(int i=1;i<=m;++i) {
                int idx1 = i - 1;
                for(int j=1;j<=n;++j) {
                        int idx2 = j - 1;
                        if(chs2[idx2]=='.') {
                                dp[i][j] = dp[idx1][idx2];
                        } else if(chs2[idx2]=='*') {
                                if(dp[idx1][idx2]) {
                                        if(chs2[idx2-1]=='.') {
                                                while(j<=n) {
                                                        dp[i][j] = true;
                                                        ++j;
                                                }
                                        } else {
                                                while(j<=n && chs2[j-1]==chs1[idx1]) {
                                                        dp[i][j] = true;
                                                        ++j;
                                                }
                                        }
                                }
                                break;
                        } else {
                                dp[i][j] = chs2[idx2]==chs1[idx1] && dp[idx1][idx2];
                        }
                }
        }
        for(int i=1;i<=n;++i) if(dp[m][i]) return true;
        return false;
}

zhanglixue 发表于 2018-2-26 01:04
写了一个o(n^2)的解法供讨论，楼主面试可能太紧张了吧，效果会适得其反。
isMatch(String s1, String s2)  ...

我研究了一下你的代码，但我没明白这个代码有没有考虑到所有substring？还有中间idx2和idx1是不是用混啦？不太明白，可以解释一下吗~谢谢

qjdehouse 发表于 2018-2-26 07:40
我研究了一下你的代码，但我没明白这个代码有没有考虑到所有substring？还有中间idx2和idx1是不是用混啦 ...

举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t
a| f  t.  f.  t.  f. f
. | f  f.  t.  f.  t. f
*| f  f.  f.  t.  t. t

举了个例子，上面是原字符串"acabb"，左边是正则表达式"a.*", 参看dp的第二行，a其实匹配了2个字串，原字符串里有两个a。相比于leetcode上的题目，转折点就在这里，原题目，第二个a应该是false。

zhanglixue 发表于 2018-2-26 09:46
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

wow!神奇！谢谢你啦！！我真的是还有很多有待提高的地方

zhanglixue 发表于 2018-2-26 09:46
举个例子吧
       a  c  a  b  b
  | t  t   t  t   t  t

我又研究了一下，发现还是有点问题，dp[i][j]的结果应该不是只依赖于dp[i - 1][j - 1]，我觉得chs2[j] == '*'的时候，还应该判断一下其他情况，因为x*可以匹配x出现0次或1次或多次，这三种情况是和dp表格前面的不同位置有关的。你举得例子如果是匹配a.*和ac的话，return的就是false了，但结果应该是true

还是多谢你给的方法啦！我完全没有想到呢

把pattern前面加上.*, 最后加上.*，再用原题的解法解行不行

qjdehouse 发表于 2018-2-26 11:47
我又研究了一下，发现还是有点问题，dp[j]的结果应该不是只依赖于dp[j - 1]，我觉得chs2[j] == '*'的时候 ...

呵呵 我随便写了一下，里面可能有问题，没检查。你可以重写一下，看看是不是有逻辑错误。

hpnhxxwn 发表于 2018-2-26 17:46
把pattern前面加上.*, 最后加上.*，再用原题的解法解行不行

那样会不会多出很多true的情况啊？

zhanglixue 发表于 2018-2-27 00:12
呵呵 我随便写了一下，里面可能有问题，没检查。你可以重写一下，看看是不是有逻辑错误。

逻辑很好！应该没有问题

qjdehouse 发表于 2018-2-28 10:57
那样会不会多出很多true的情况啊？

我理解的题意是，只要在string里面找到一个substring match就行了。.*match 前面的和后面的，当中match上pattern就行。这样理解对吗？

从我工作的经验来看，比如说用vim，.*xxx.*就能match上xxx。