[分析]
两字符串相同或者长度差异大于等于2都不符合要求,只需要检查那些长度相同或者相差为1的情况。逐个字符检查,发现第一个差异字符,若s和t长度相等将s中字符替换为t中字符,若不等则在s中插入t当前字符,然后跳出检查循环。若检查过程无差异字符(说明长度差1)或者消除发现的第一个差异后两字符串相等说明两字符串编辑距离为1.
这个思路和实现参考
https://leetcode.com/discuss/42379/4ms-11-lines-c-solution-with-explanations,自己写的丑代码就不粘贴了
public class Solution {
public boolean isOneEditDistance(String s, String t) {
if (s == null || t == null || s.equals(t)) return false;
int sLen = s.length(), tLen = t.length();
if (sLen > tLen) return isOneEditDistance(t, s);
if (sLen + 1 < tLen) return false; // |sLen - tLen| >= 2
boolean misMatch = false;
for (int i = 0; i < sLen; i++) {
if (s.charAt(i) != t.charAt(i)) {
if (sLen == tLen) {// replace the first diff char is s with char of t
s = s.substring(0, i) + t.charAt(i) + s.substring(i + 1, sLen);
} else { // insert curr char of t
s = s.substring(0, i) + t.charAt(i) + s.substring(i, sLen);
}
misMatch = true;
break;
}
}
return !misMatch || s.equals(t);
}
}
分享到:
相关推荐
javascript js_leetcode题解之161-one-edit-distance.js
《在IDE中高效进行LeetCode练习:leetcode-editor的深度解析》 在编程学习与技能提升的过程中,LeetCode作为一款广受欢迎的在线编程挑战平台,帮助众多开发者锻炼算法思维,提高编程能力。而为了进一步提升练习体验...
leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
LeetCode Editor 7.4 版本的下载是一个名为 "leetcode-editor" 的压缩包文件。这个压缩包的导入过程非常简单,只需要将它直接拖入 IDEA 界面,IDEA 会自动识别并安装插件。这种方式使得安装过程无需额外的步骤,对于...
leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
python python_leetcode题解之161_One_Edit_Distance.py
《PyPI官网下载 | leetcode-export-1.1.tar.gz》 在编程世界里,LeetCode是一个备受程序员喜爱的在线平台,它提供了大量的算法题目,帮助开发者提升编程技能和解决问题的能力。而Python作为一门广泛使用的高级编程...
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
`swift-Swif-LeetCode-Utils` 是一个实用工具库,它为Swift程序员提供了方便快捷的方法来处理这些问题。这个项目可以帮助你更高效地进行LeetCode上的编程练习,提升你的解决方案的可读性和简洁性。 首先,让我们...
java java_leetcode-115-distinct-subsquences
java java_leetcode-112-path-sum
java java_leetcode-101-symmetric-tree
java java_leetcode-100-same-tree
java java_leetcode-110-balanced-binary-tree
java java_leetcode-73-set-matrix-zeroes