米哈游（原神）一面算法原题

特斯拉裁员 10%

昨天，特斯拉发全员信，宣布全球裁员超 10%。

在内部信中，特斯拉 CEO 埃隆马斯克表示：”多年来，我们发展迅速，在全球范围内开设了多家工厂。随着增长，某些部门出现了角色和工作职能的重复。当我们为公司下一阶段的增长做好准备时，聚焦各方面以降本增效是极其重要的。”

这几乎就是上周写的 亚马逊裁员,涉及中国区 的翻版。

马斯克还表示道”裁员是艰难的决定，没有什么比这更让我讨厌的了，但又必须这么做”。

嗯，怎么说就怎么听吧，但至少是收购推特后大面积裁员时没说过的。

根据特斯拉的财报，截止 2023 年 12 月底，特斯拉全球拥有员工约 14W，本次裁员 10%，即涉及 1.4W 人。

…

今天来做一道和之前读者投稿的「米哈游」一面算法题相关性较大的题目。

题目描述

平台：LeetCode

题号：583

给定两个单词s1和s2，找到使得s1和s2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

输入:"sea","eat"

输出:2

解释:第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

提示：

• 给定单词的长度不超过
  

  。
  

• 给定单词中的字符只含有小写字母。
  

转换为 LCS 问题

首先，给定两字符 s1 和 s2，求经过多少次删除操作，可使得两个相等字符串。

该问题等价于求解两字符的「最长公共子序列」，若两者长度分别为

和

，而最长公共子序列长度为

，则

即为答案。

对「最长公共子序列（LCS）」不熟悉的同学，可以看 (题解) 1143. 最长公共子序列。

「

）时形成的「最长公共子序列（LCS）」长度。」

当有了「状态定义」之后，基本上「转移方程」就是呼之欲出：

• s1[i]==s2[j] :
  

  服务器托管

  。代表
  「必然使用

  与

  时」 LCS 的长度。
  

• s1[i]!=s2[j] :
  

  。代表
  「必然不使用

  （但可能使用

  ）时」 和
  「必然不使用

  （但可能使用

  ）时」 LCS 的长度。
  

可以发现，上述两种讨论已经包含了「不使用

和

」、「仅使用

」、「仅使用

服务器托管

」和「使用

和

」四种情况。

虽然「不使用

和

」会被

和

重复包含，但对于求最值问题，重复比较并不想影响答案正确性。

因此最终的

为上述两种讨论中的最大值。

一些编码细节：

通常会习惯性往字符串头部追加一个空格，以减少边界判断（使下标从 1 开始，并很容易构造出可滚动的「有效值」）。但实现上，不用真的往字符串中最佳空格，只需在初始化动规值时假定存在首部空格，以及对最后的 LCS 长度进行减一操作即可。

Java 代码：

classSolution{
publicintminDistance(Strings1,Strings2){
char[]cs1=s1.toCharArray(),cs2=s2.toCharArray();
intn=s1.length(),m=s2.length();
int[][]f=newint[n+1][m+1];
//假定存在哨兵空格，初始化f[0][x]和f[x][0]
for(inti=0;i0]=1;
for(intj=0;j0][j]=1;
for(inti=1;i
for(intj=1;j
f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
if(cs1[i-1]==cs2[j-1])f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
}
}
intmax=f[n][m]-1;//减去哨兵空格
returnn-max+m-max;
}
}

C++ 代码：

classSolution{
public:
intminDistance(strings1,strings2){
intn=s1.size(),m=s2.size();
vectorvectorint>>f(n+1,vectorint>(m+1));
for(inti=0;i0]=1;
for(intj=0;j0][j]=1;
for(inti=1;i
for(intj=1;j
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(s1[i-1]==s2[j-1])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
intmax=f[n][m]-1;
returnn-max+m-max;
}
};

Python 代码：

classSolution:
defminDistance(self,s1:str,s2:str)->int:
n,m=len(s1),len(s2)
f=[[1]*(m+1)for_inrange(n+1)]
foriinrange(1,n+1):
forjinrange(1,m+1):
f[i][j]=max(f[i-1][j],f[i][j-1])
ifs1[i-1]==s2[j-1]:
f[i][j]=max(f[i][j],f[i-1][j-1]+1)
max_val=f[n][m]-1
returnn-max_val+m-max_val

TypeScript 代码：

functionminDistance(s1:string,s2:string):number{
constn=s1.length,m=s2.length;
constf:number[][]=Array(n+1).fill(0).map(()=>Array(m+1).fill(1));
for(leti=1;i
for(letj=1;j
f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
if(s1[i-1]===s2[j-1]){
f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
}
}
}
constmax=f[n][m]-1;
returnn-max+m-max;
};

• 时间复杂度：
  

  
  

• 空间复杂度：
  

  
  

序列 DP

上述解决方案是套用了「最长公共子序列（LCS）」进行求解，最后再根据 LCS 长度计算答案。

而更加契合题意的状态定义是根据「最长公共子序列（LCS）」的原始状态定义进行微调：「定义

）时形成相同字符串的最小删除次数。」

同理，不失一般性的考虑

该如何计算：

• s1[i]==s2[j]：
  

  ，代表可以不用必然删掉
  

  和
  

  形成相同字符串；
  

• s1[i]!=s2[j]：
  

  ，代表至少一个删除
  

  和
  

  中的其中一个。
  

为上述方案中的最小值，最终答案为

。

Java 代码：

classSolution{
publicintminDistance(Strings1,Strings2){
char[]cs1=s1.toCharArray(),cs2=s2.toCharArray();
intn=s1.length(),m=s2.length();
int[][]f=newint[n+1][m+1];
for(inti=0;i0]=i;
for(intj=0;j0][j]=j;
for(inti=1;i
for(intj=1;j
f[i][j]=Math.min(f[i-1][j]+1,f[i][j-1]+1);
if(cs1[i-1]==cs2[j-1])f[i][j]=Math.min(f[i][j],f[i-1][j-1]);
}
}
returnf[n][m];
}
}

C++ 代码：

classSolution{
public:
intminDistance(strings1,strings2){
intn=s1.size(),m=s2.size();
vectorvectorint>>f(n+1,vectorint>(m+1));
for(inti=0;i0]=i;
for(intj=0;j0][j]=j;
for(inti=1;i
for(intj=1;j
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(s1[i-1]==s2[j-1])f[i][j]=min(f[i][j],f[i-1][j-1]);
}
}
returnf[n][m];
}
};

Python 代码：

classSolution:
defminDistance(self,s1:str,s2:str)->int:
n,m=len(s1),len(s2)
f=[[0]*(m+1)for_inrange(n+1)]
foriinrange(n+1):
f[i][0]=i
foriinrange(m+1):
f[0][i]=i
foriinrange(1,n+1):
forjinrange(1,m+1):
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1)
ifs1[i-1]==s2[j-1]:
f[i][j]=min(f[i][j],f[i-1][j-1])
returnf[n][m]

TypeScript 代码：

functionminDistance(s1:string,s2:string):number{
constn=s1.length,m=s2.length;
constf:number[][]=Array.from({length:n+1},()=>Array(m+1).fill(0));
for(leti=0;i0]=i;
for(leti=0;i0][i]=i;
for(leti=1;i
for(letj=1;j
f[i][j]=Math.min(f[i-1][j]+1,f[i][j-1]+1);
if(s1.charAt(i-1)==s2.charAt(j-1))f[i][j]=Math.min(f[i][j],f[i-1][j-1]);
}
}
returnf[n][m];
};

• 时间复杂度：
  

  
  

• 空间复杂度：
  

  
  

最后

给大伙通知一下 ：

全网最低价 LeetCode 会员目前仍可用！！！

年度会员：有效期加赠两个月！！; 季度会员：有效期加赠两周！！

年度会员：获 66.66 现金红包！！; 季度会员：获 22.22 现金红包！！

年度会员：参与当月丰厚专属实物抽奖（中奖率 > 30%)！！

专属链接：leetcode.cn/premium/?promoChannel=acoier

我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。

欢迎关注，明天见。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地