报一个Jet Karat电面顺便求问一道题最优解

前几分钟讲一下背景
然后限时20分钟给一段大概150-200行的代码做code review，把问题和解决方案写在代码边上

LZ这里做review过于仔细，comment也写得太细，最后时间不太够，最后有一个大的问题只能说一说，没来得及写

然后给了一道题：
给两个用户访问一个

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

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

相同，但是在list B里不是连续的

这道题我想了20分钟没想出比暴力解更好的方法，最后无奈之下把暴力解写了，复杂度是M*N，求问版上大神此题有没有比M*N更好的解法

顺便贴个应该符合面试官心意的DP代码好了

1. class Solution {
   
2. public:
   
3.     int longestCommonSubstring(string &A, string &B) {
   
4.         vector<vector<int>> dp(A.length() + 1, vector<int>(B.length() + 1));
   
5.         int ans=0;
   
6.         for(int i=0;i<=A.length();i++)dp[i][0]=0;
   
7.         for(int i=0;i<=B.length();i++)dp[0][i]=0;
   
8.         for(int i=0;i<A.length();i++){
   
9.             for(int j=0;j<B.length();j++){
   
10.                 if(A[i]==B[j]){
    
11.                     ans=max(ans,dp[i][j]+1);
    
12.                     dp[i+1][j+1]=dp[i][j]+1;
    
13.                 }
    
14.             }
    
15.         }
    
16.         return ans;
    
17.     }
    
18. };

复制代码

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

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

这题用DP才是MN，参考longest substring。不知道你说的暴力是什么样的可以弄到MN。

请问lz这是申请jet什么职位的电面呢

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

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

我intuit的oa是这道题。
最优的应该是用dp，m*n的时间，constant的空间（不建二维表，只记录i - 1，j - 1的结果）。

Liddy_L 发表于 2018-2-22 16:08
我intuit的oa是这道题。
最优的应该是用dp，m*n的时间，constant的空间（不建二维表，只记录i - 1，j - 1 ...

不建二維表的話，需要一維表然後從后往前掃，是麽？

cai_lw 发表于 2018-3-14 10:20
顺便贴个应该符合面试官心意的DP代码好了

这里应该要输出的是list，然后其实也可以优化空间吧，2D->1D，经典背包优化