LeetCode刷题实战161:相隔为1的编辑距离
共 1521字,需浏览 4分钟
·
2021-01-23 05:45
Given two strings S and T, determine if they are both one edit distance apart.
题意
示例 1:
输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。
示例 2:
输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。
示例 3:
输入: s = "1203", t = "1213"
输出: true
解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。
解题
class Solution {
public boolean isOneEditDistance(String s, String t) {
int ns = s.length();
int nt = t.length();
//交换
if (ns > nt)
return isOneEditDistance(t, s);
//长度差超过1
if (nt - ns > 1)return false;
//找到不同的字符
for (int i = 0; i < ns; i++)
if (s.charAt(i) != t.charAt(i))
//如长度不同,那么两字符串后面应该相同
if (ns == nt)
return s.substring(i + 1).equals(t.substring(i + 1));
//如长度不同,那么必须在s[i]插入t[i],所以要保证s.substring(i).equals(t.substring(i + 1))
else
return s.substring(i).equals(t.substring(i + 1));
return (ns + 1 == nt);
}
}