注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(75)-两个字符串上的删除操作[算法]  

2018-04-14 03:59:35|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题:给你两个单词word1word2,请问至少需要几次删除操作使得word1word2变得一样?每一步你都可以从word1或者word2里删除一个字符。例如如果输入两个单词"sea""eat",我们至少需要两步删除操作,分别删除第一个单词的's'和第二个单词的't',使得它们变成相同的"ea"


分析:这是LeetCode的第583题。


如果我们熟悉经典的动态规划问题最长公共子串(LCS, Longest Common Subsequence),那么这个问题实际上最长公共字串的应用。这是因为我们的目标是删除一些字符之后word1word2相同,也就是剩下的是两个字符串的公共子串。剩下的公共子串越长,那么需要的删除操作就越少。

于是我们可以写出如下的函数:


程序员面试题精选100题(75)-两个字符串上的删除操作[算法] - 何海涛 - 微软、Google等面试题

接下来我们来解决其中的关键问题,也就是如果求两个字符串的最长公共子串。

解法一:空间效率O(n^2)


由于这是一个求解最优解的问题(“最长”公共子串),我们可以尝试应用动态规划。应用动态规划的第一步找出状态转移函数。我们用函数f(i,j)表示第一个字符串s1的前i个字符组成的子字符串和第二个字符串s2的前j个字符组成的子字符串的最长公共子串的长度。


我们分两种情况讨论这个函数。如果s1中的第i个字符和s2中的第j个字符相同,f(i,j)等于f(i-1,j-1)+1。这相当于在s1的前i-1个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的基础上增加了一个公共的字符。


如果s1中的第i个字符和s2中的第j个字符不同,f(i,j)等于f(i-1,j)f(i,j-1)的较大值。既然s1中的第i个字符和s2中的第j个字符不同,我们可以忽略s1中的第i个字符,去看看在s1的前i-1个字符组成的子字符串和s2的前j个字符组成的子字符串的最长公共子串的长度,这就是f(i-1,j)的值。同样,我们也可以忽略s2中的第j个字符,去看看在s1的前i个字符组成的子字符串和s2的前j-1个字符组成的子字符串的最长公共子串的长度,这就是f(i,j-1)的值。


由于状态转移函数有两个变量ij,我们可以用一个二维矩阵来存储f(i,j)的值。以下就是基于二维矩阵的代码:


程序员面试题精选100题(75)-两个字符串上的删除操作[算法] - 何海涛 - 微软、Google等面试题
 

如果两个字符串的长度分别是mn,上述代码的时间和空间复杂度都是O(mn)


解法二:空间效率O(n)


我们仔细分析上述代码,就能发现在求解dp[i][j]的时候只用到了dp[i-1][j-i]dp[i-1][j]dp[i][j-1],这三个值要么位于二维矩阵dp的第i-1行,要么位于dp的第i行。因此求任意一个dp[i][j]的时候,我们只要矩阵中的第i-1行和第i行这两行就够了,并不是真正需要保留所有的m+1行(假设m为第一个字符串s1的长度)。这样空间复杂度就降低到O(n)了。


接下来我们看能不能进一步减少空间的使用,只保留二维矩阵dp中的一行,也就是只保留一个一维数组。如果只保留二维矩阵中的一行,第i-1行第j-1的数值(即f(i-1,j-1))和第ij-1列的数值(即f(i,j-1))都对应到一维数组中的第j-1个数值。可是我们在求f(i,j)又同时需要第i-1行第j-1列的数值和第ij-1列的数值,因此我们需要确保它们两个在使用之前不能相互覆盖。


我们注意到f(i-1,j-1)的值只是在求解f(i,j)有用,之后再也不需要。因此我们在求解f(i,j)的时候,先不把f(i,j-1)的值写入到一维数组,而是用一个临时变量保存。在求解f(i,j)之后,再把f(i,j-1)写入到一维数组。此时即使把f(i-1,j-1)的值覆盖,也不会有任何问题。


基于上面的优化,我们可以写出如下代码:

程序员面试题精选100题(75)-两个字符串上的删除操作[算法] - 何海涛 - 微软、Google等面试题
 

上述代码仍然需要两重循环,因此时间复杂度仍然是O(mn)。由于只需要一个一维数组,因此空间复杂度是O(n)

举一反三:

给我们两个字符串s1s2,请问如何删除字符使得两个字符串相同,并且被删除的字符的ASCII值的和最小?求被删除的字符的ASCII值的和的最小值。


这是LeetCode的第712题。


这实际上前面问题的变种。我们如果能求出ASCII值最大的公共字串,那么其他的就是被删除的ASCII值的和最小的字符。因此我们我们只需要在前面代码的基础上稍微改改,就能解决这个问题。

参考代码如下:

程序员面试题精选100题(75)-两个字符串上的删除操作[算法] - 何海涛 - 微软、Google等面试题

 

本文转载自微信公众号青云算法扫描下面的二维码,关注“青云算法”微信公众号,学习更多高频算法面试题的解法。

程序员面试题精选100题(65)-每天的温度[算法] - 何海涛 - 微软、Google等面试题

  评论这张
 
阅读(893)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018