### 题目

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

### 字符串的编辑距离

1. insert: 插入一个字符
2. modify: 修改一个字符
3. delete: 删除一个字符

1. acd: 删除了b
2. adcd: b修改成d
3. aabcd: 在b之前插入了a

### 动态规划

  |   a b c d     s
-+--------------
| 0 1 2 3 4
a| 1 0 0 0 0
a| 2 0 0 0 0
b| 3 0 0 0 0
c| 4 0 0 0 0
d| 5 0 0 0 0
|
t


1. 上点upper: [x-1,y]
2. 左点left: [x,y-1]
3. 左上角点corner: [x-1,y-1]

Val[x,y] = Min([x-1,y]+1,[x,y-1]+1), (t[x-1] == s[y-1])? [x-1,y-1] : [x-1,y-1] + 1

#### 代码

class Solution {
public boolean isOneEditDistance(String s, String t) {
int ls = s.length(), lt = t.length();
if (Math.abs(ls-lt) > 1) { return false; }
if (s.equals(t)) { return false; }
int[][] matrix = new int[ls+1][lt+1];
for (int i = 1; i <= lt; i++) {
matrix[0][i] = matrix[0][i-1] + 1;
}
for (int i = 1; i <= ls; i++) {
matrix[i][0] = matrix[i-1][0] + 1;
}
for (int i = 1; i <= ls; i++) {
for (int j = 1; j <= lt; j++) {
matrix[i][j] = Math.min(Math.min(matrix[i-1][j],matrix[i][j-1]) + 1, (s.charAt(i-1) == t.charAt(j-1))? matrix[i-1][j-1] : matrix[i-1][j-1] + 1);
}
}
return (matrix[ls][lt] == 1)? true : false;
}
}


### 用一维数组就能完成动态规划

#### 代码

class Solution {

public boolean isOneEditDistance(String s, String t) {
int ls = s.length(), lt = t.length();
if (Math.abs(ls-lt) > 1) { return false; }
if (s.equals(lt)) { return false; }
int longer = Math.max(ls,lt);
int shorter = Math.min(ls,lt);
if (s.length() < t.length()) { // make sure s is the longer string
String temp = s;
s = t;
t = temp;
}
int min = 0;
int[] memo = new int[longer+1];
for (int i = 1; i <= longer; i++) {
memo[i] = memo[i-1] + 1;
}
int corner = 0, col = 0;
for (int i = 1; i <= shorter; i++) {
corner = i - 1; col = i;
if (corner > 1 && min > 1) { // 剪枝
return false;
}
min = corner;
for (int j = 1; j <= longer; j++) {
int oldVal = memo[j];
memo[j] = Math.min(Math.min(memo[j],col) + 1, (t.charAt(i-1) == s.charAt(j-1))? corner : corner + 1);
min = Math.min(min, memo[j]);
corner = oldVal;
col = memo[j];
}
}
return (memo[longer] == 1)? true : false;
}
}


### 递归动态规划

#### 代码

class Solution {

private String strS;
private String strT;
private int lenS;
private int lenT;

public boolean isOneEditDistance(String s, String t) {
strS = s;
strT = t;
lenS = s.length();
lenT = t.length();
int diff = lenS - lenT;
if (diff < -1 || diff >1) { return false; }
int distance = dp(0,0);
return distance == 1;
}

private int dp(int ps, int pt) {
if (ps == lenS && pt == lenT) { return 0; }
int movePs = Integer.MAX_VALUE, movePt = movePs, moveBoth = movePs;
if (ps < lenS) { movePs = dp(ps+1,pt) + 1; }
if (pt < lenT) { movePt = dp(ps,pt+1) + 1; }
if (ps < lenS && pt < lenT) { moveBoth = dp(ps+1,pt+1) + ((strS.charAt(ps) == strT.charAt(pt))? 0 : 1); }
return Math.min(Math.min(movePs,movePt),moveBoth);
}

}


### 反而朴素的启发式方法能通过

#### 代码

class Solution {

public boolean isOneEditDistance(String s, String t) {
int lenS = s.length();
int lenT = t.length();
int diff = lenS - lenT;
if (diff < -1 || diff > 1) { return false; }
for (int i = 0; i < Math.min(lenS,lenT); i++) {
if (s.charAt(i) != t.charAt(i)) {
if ((diff == 0) && s.substring(i+1).equals(t.substring(i+1))) { return true; }
if ((diff == 1) && s.substring(i+1).equals(t.substring(i))) { return true; }
if ((diff == -1) && s.substring(i).equals(t.substring(i+1))) { return true; }
return false;
}
}
return diff != 0;
}

}