interviews/leetcode/string/EditDistance.java at master · codingOnGithub/interviews · GitHub

41 lines (32 loc) · 1.17 KB

// 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

public class EditDistance {

public int minDistance(String word1, String word2) {

int m = word1.length();

int n = word2.length();

int[][] dp = new int[m + 1][n + 1];

for(int i = 0; i <= m; i++) {

dp[i][0] = i;

}

for(int i = 0; i <= n; i++) {

dp[0][i] = i;

}

for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) {

if(word1.charAt(i) == word2.charAt(j)) {

dp[i + 1][j + 1] = dp[i][j];

} else {

int a = dp[i][j];

int b = dp[i][j + 1];

int c = dp[i + 1][j];

dp[i + 1][j + 1] = Math.min(a, Math.min(b, c));

dp[i + 1][j + 1]++;

}

return dp[m][n];

}

Expand file tree