非死不可店面跪经

也可以把pattern变成.*pattern.*, 这样就可以直接默写LC10的答案了

hueyhy 发表于 2018-3-24 08:48
可能楼主过于想套用lc10的解反而把问题弄复杂了.这个和lc10唯一的区别就是lc10的true是s1, s2都走到头. 从 ...

是的是的，你说的很对~我也是后来一想 确实是这样！谢谢你的分享~~

xiaotdl 发表于 2018-3-24 09:10
也可以把pattern变成.*pattern.*, 这样就可以直接默写LC10的答案了

我觉得这个方法也很棒！

Po一个答案~其实和原题就差三行代码

1. public boolean isMatch(String s, String p) {
   
2.         int n1 = s.length(), n2 = p.length();
   
3.         boolean[][] dp = new boolean[n1 + 1][n2 + 1];
   
4.         
   
5.         dp[0][0] = true;
   
6.         
   
7.         // 初始化match nothing
   
8.         for (int j = 1; j <= n2; j++) {
   
9.             if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2];
   
10.             }
    
11.         }
    
12. 
    
13.         for (int i = 1; i <= n1; i++) {
    
14.             for (int j = 1; j <= n2; j++) {
    
15.                 if (p.charAt(j - 1) == '*') {// abc ab*c
    
16.                     dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
    
17.                 } else {
    
18.                     dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
    
19.                 }
    
20.             }
    
21.         }
    
22.         
    
23. // 这是和原题唯一不同的地方
    
24. for (int i = 1; i <= n1; i++) {
    
25.     if (dp[i][n2]) return true;
    
26.         }
    
27.         
    
28.         return false;
    
29. }

复制代码

tonyabracadabra 发表于 2018-6-3 17:39
Po一个答案~其实和原题就差三行代码

[mw_shl_code=java,true]public boolean isMatch(String s, String  ...

这个有很多情况没有考虑吧 ？
dp[i][n2] 是 指   s.substring (0, i)   和  p.substring(0, n2) 是否 match，  但是结果也有可能是  s.substirng(x, i) 和 p match,  0<= x <n1

补充内容 (2018-6-10 12:59):
dp [  i ]  [  n2 ]

34楼那个答案错的，简单反例就是 string = "zzzabc", pattern = "abc"

在一个字符串里找子串本身就要kmp之类的才能做到O(n)，个人感觉做出n3应该可以了吧，要是硬要做n2估计kmp变种之类的

不过fb现在出啥难题也不奇怪就是了。。。

补充内容 (2018-6-10 13:33):
想多了，只要找起点就行，n^2稍微改改，遇到与pattern第一个字符相同的直接给true当起点就行

LZ各位你们仔细看看lc10，不是lc44

补充内容 (2018-7-29 05:01):
never mind, I mess it up...

liweiheng 发表于 2018-7-29 04:57
LZ各位你们仔细看看lc10，不是lc44

I mean LS