地址 https://leetcode-cn.com/problems/one-away-lcci/
字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑。 示例 1: 输入: first = "pale" second = "ple" 输出: True 示例 2: 输入: first = "pales" second = "pal" 输出: False
解答
可以考虑使用动态规划进行解答
这里介绍下另一种做法
根据题意,只能添删换三种操作变换成另一字符串,
等价于两个字符串长度不能相差大于1,不同之处不能大于1.
我们分为长度差为1和长度相同两种情况分别解决
class Solution { public: bool oneEditAway(string first, string second) { if ((first.size() + second.size()) == 1 || (first.size() + second.size()) == 0) { return true; } if ((int)second.size() - (int)first.size() > 1) return false; if ((int)second.size() - (int)first.size() < -1) return false; if (first.size() == second.size()) { int optCount = 0; for (int i = 0; i < first.size(); i++) { if (first[i] != second[i]) { optCount++; } if (optCount > 1) return false; } } else { if (first.size() > second.size()) { swap(first, second); } int count = 0; int l = 0; int r = 0; while (l < first.size() && r < second.size()) { if (first[l] == second[r]) { l++; r++; } else { count++; r++; } if (count > 1) return false; } } return true; } };