https://leetcode.com/problems/edit-distance/#/description
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character b) Delete a character c) Replace a character
package go.jacob.day708; /** * 72. Edit Distance * @author Jacob * */ public class Demo3 { /* * 动态规划应用 */ public int minDistance(String word1, String word2) { if (word1 == null || word2 == null) return 0; int[][] res = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i <= word1.length(); i++) { res[i][0] = i; } for (int j = 0; j <= word2.length(); j++) { res[0][j] = j; } for (int i = 0; i < word1.length(); i++) { for (int j = 0; j < word2.length(); j++) { if (word1.charAt(i) == word2.charAt(j)) res[i + 1][j + 1] = res[i][j]; else { res[i + 1][j + 1] = 1 + min(res[i + 1][j], res[i][j + 1], res[i][j]); } } } return res[word1.length()][word2.length()]; } private int min(int i, int j, int k) { int min = Math.min(i, j); min = Math.min(min, k); return min; } }
