161. One Edit Distance

 1     public boolean isOneEditDistance(String s, String t) {
 2         if(s == null ||  t == null) {
 3             return false;
 4         }
 5         return editDistance(s, t) == 1;
 6     }
 7     
 8     private int editDistance(String s, String t) {
 9         int lenS = s.length();
10         int lenT = t.length();
11         if(lenS == 0) {
12             return lenT;
13         } else if(lenT == 0){
14             return lenS;
15         }
16         int[][] res = new int[lenS][lenT];
17         res[0][0] = s.charAt(0) == t.charAt(0) ? 0: 1;
18         for(int i = 1; i < lenS; i++) {
19             res[i][0] = res[i-1][0] + (s.charAt(i) == t.charAt(0) ? 0: 1);
20         }
21         for(int i = 1; i < lenT; i++) {
22             res[0][i] = res[0][i-1] + (s.charAt(0) == t.charAt(i)? 0: 1);
23         }
24         for(int i = 1; i < lenS; i++) {
25             for(int j = 1; j < lenT; j++) {
26                 if(s.charAt(i) == t.charAt(j)) {
27                     res[i][j] = res[i-1][j-1];
28                 } else {
29                     res[i][j] = Math.min(Math.min(res[i-1][j-1], res[i-1][j]), res[i][j-1]) + 1;
30                 }
31             }
32         }
33         return res[lenS - 1][lenT - 1];
34     }