非死不可店面跪经

2.13 做完的电面，刚刚收到消息说not moving forward了。。。

题目是一道hard题，leetcode 10改。给一个regression expression，问在另一个string里面有没有和他匹配的substring。面之前我刚刚看过这一题，还以为撞了大

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

匆结束。。。

本来觉得很有希望的，哎。。。期待落空，拒信连连的滋味真不好受。。。也不知道问题出在了哪里，应该还是自己能力不够，经验不足吧

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. }

复制代码

只是看所有subarray，中间和LC一样做dp，match了就return，是不是O(n^3)啊？
input是s和p, p是pattern的话，
在原本LC题的两层循环外面再套一层循环s的每一位，相当于把每一位设为substring的起始点
大概意思就是

for(int i = 0; i < s.length(); i++){
         初始化一个新的boolean[][]
         for(int j = i+1; j < s.length()+1; j++){
               for(int k = 1; k < p.length()+1; k++){
                         这段和LC一样
               }
               if(dp[j-i][p.length()]) return true; //说明substring已经match了p了
         }
}
return false;

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

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

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

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

楼主投的是new grad SDE吗？看面经感觉题目难度层次不齐。完全靠运气。

yexiaojiaycc 发表于 2018-2-24 08:05
楼主投的是new grad SDE吗？看面经感觉题目难度层次不齐。完全靠运气。

是的是的，我感觉他们对面试表现的要求应该是蛮高的，可能题目简单一些会容易过一点吧

qjdehouse 发表于 2018-2-24 08:19
是的是的，我感觉他们对面试表现的要求应该是蛮高的，可能题目简单一些会容易过一点吧

是啊，宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。

目前还是传说中的一题nohire，两题hire，三题strong hire……
我感觉他们期待的是这题30行的O(n2)解法你要bug free 15分钟之内秒杀，然后面试官可能还藏了一题期待给你hire……

不过这题DP怎么做到O(n4)的。。。不是O(n*m)跑一遍就完了吗(我倒是知道O(2^(n+m))的……)

要是没见过真的只能说自己刷题不行了……

vtiaocao 发表于 2018-2-24 09:04
目前还是传说中的一题nohire，两题hire，三题strong hire……
我感觉他们期待的是这题30行的O(n2)解法你要 ...

因为他问的题目是在一个string里找匹配的substring，我第一个想到的就是遍历所有的substring起点和终点。二维DP填表的复杂度是n^2, 找substringn^2, 就是n^4了

莲藕熊软软 发表于 2018-2-24 08:48
只是看所有subarray，中间和LC一样做dp，match了就return，是不是O(n^3)啊？
input是s和p, p是pattern的话 ...

是的n^3就可以解决了~和substring比较同时填dp，遇到不对的就扔掉重新开始，这个是最后面试官问我优化时讨论说的

yexiaojiaycc 发表于 2018-2-24 08:57
是啊，宁愿做2个medium的也不想遇到一个hard的。楼主运气不好。。。

找工作要么得有很强的实力，要么有不错的运气。只能继续努力提高实力了！

qjdehouse 发表于 2018-2-24 09:23
因为他问的题目是在一个string里找匹配的substring，我第一个想到的就是遍历所有的substring起点和终点。 ...

优化之后n^3，不知道还有没有更好的方法。以我的能力十五分钟根本完成不了