One Edit Distance
2020-07-07 本文已影响0人
瞬铭
https://leetcode.com/problems/one-edit-distance/
给定word1,word2 计算从是否可以一步从word1变到word2
Example 1:
Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.
Example 2:
Input: s = "cab", t = "ad"
Output: false
Explanation: We cannot get t from s by only one step.
Example 3:
Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.
与Edit Distance比较类似,但是不用那么复杂把最小Distance求出,只用遵循规则计算是否一步能到
public Boolean isOneEditDistance(String s, String t) {
int sLen = s.length();
int tLen = t.length();
if ((Math.abs(sLen - tLen) > 1)) {
return false;
}
if (sLen > tLen) {
return isOneEditDistance(s.substring(0, sLen - 1), t);
} else if (sLen < tLen) {
return isOneEditDistance(s, t.substring(0, t.length() - 1));
}
return s.equals(t) ? true : isOneEditDistance(s.substring(0, sLen - 1), t.substring(0, t.length() - 1));
}