程序员面试金典好题/面试题 01.05. 一次编辑
2022/2/11 11:15:54
本文主要是介绍程序员面试金典好题/面试题 01.05. 一次编辑,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
面试题 01.05. 一次编辑
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。
示例 1:
输入: first = "pale" second = "ple" 输出: True
示例 2:
输入: first = "pales" second = "pal" 输出: False
解题方法:
动态规划法:
- 找出最小编辑次数(
dp[i][j]
的含义) - 初始化(一边的字符串为空):
dp[0][j]
= j;dp[0][i]
= i;
- 动态转化方程
- 如果当前字符相等,就等于前一个字符的编辑次数(次数不变)
- 如果不相等,就等于前一个字符的最小编辑次数 + 1
- 时间复杂度O(nm)
class Solution { public: bool oneEditAway(string first, string second) { int n = first.size(); int m = second.size(); if(n - m > 1) return false; vector<vector<int>> dp(n + 1,vector<int>(m + 1,0)); //当第一个字符串为"" for (int j = 1; j <= m; j++) { dp[0][j] = j; } //当第二个字符串为"" for (int i = 1; i <= n; i++) { dp[i][0] = i; } for(int i = 1; i <= n;i++) { for(int j = 1; j <= m;j++) { if(first[i - 1] == second[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1}); } } int SizeMax = max(n,m); if(dp[n][m] > 1) return false; return true; } };
双指针(推荐)
- 判断字符串长度
- 如果大于1就说明无法一次编辑实现
- 如果等于1,说明第一个比第二个长,在second上需要加一个字符(加减是一样的)
- 如果小于1,说明第一个比第二个断,在second上需要减一个字符
- 如果等于0,说明需要改变second上的字符.
- 同时遍历两个字符串,如果不同就根据情况编辑,记录编辑次数.如果大于1就返回false;
- 时间复杂度O(max(n,m))
class Solution { public: bool oneEditAway(string first, string second) { int n = first.size(); int m = second.size(); int len = n-m; if (abs(len) > 1) return false; int count=1; for (int i = 0,j=0; i < n &&j < m; i++,j++) { if (first[i]!=second[j]) { if (len==1) //second添加一个字符 j--; else if (len==-1) //second删除一个字符 i--; count--; //编辑second的字符 } if (count<0) //大于一次编辑就失败 return false; } return true; } };
这篇关于程序员面试金典好题/面试题 01.05. 一次编辑的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了