161. One Edit Distance

发表于 | 分类于

Given two strings S and T, determine if they are both one edit distance apart.

解法1：

这题一开始如果用dp做的话需要O(MN)的复杂度，TLE了。那么一定有更简便的方法。
这里呢用到了edit distance的性质。对于edit distance为１的两个string,只可能存在下面三种情况。
长度相等 => 有且仅有一个字符不一样
长度不相等，　那么如果删掉左面string的一个字符或者是右面的一个字符。
最后还要比较一下两者的长度是否只差１。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        for (int i = 0; i < Math.min(m, n); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i+1).equals(t.substring(i+1));
                } else if (m > n) {
                    return s.substring(i+1).equals(t.substring(i));
                } else {
                    return s.substring(i).equals(t.substring(i+1));
                }
            }
        }
        return Math.abs(m - n) == 1;
    }
}