1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
public class EditDistance { public int minDistance(String word1, String word2) { if (word1 == null && word2 == null) { return 0; } if (word1 == null || word1.isEmpty()) { return word2.length(); } if (word2 == null || word2.isEmpty()) { return word1.length(); } int[][] map = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i <= word1.length(); i++) { map[i][0] = i; } for (int i = 0; i <= word2.length(); i++) { map[0][i] = i; } for (int i = 0; i < word1.length(); i++) { char c1 = word1.charAt(i); for (int j = 0; j < word2.length(); j++) { char c2 = word2.charAt(j); if (c1 == c2) { map[i + 1][j + 1] = map[i][j]; } else { int r1 = map[i][j + 1] + 1; int r2 = map[i][j] + 1; int r3 = map[i + 1][j] + 1; map[i + 1][j + 1] = Math.min(r1, Math.min(r2, r3)); } } } return map[word1.length()][word2.length()]; } }
|