Edit Distance

#100daysofcode #java #algorithms #programming

Description

Solution

import java.util.*;

class Solution {
    public int solve(String a, String b) {
        int aLength = a.length(), bLength = b.length();
        int[][] dp = new int[aLength + 1][bLength + 1];

        for (int i = 0; i <= aLength; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= bLength; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= aLength; i++) {
            char aChar = a.charAt(i - 1);
            for (int j = 1; j <= bLength; j++) {
                char bChar = b.charAt(j - 1);
                if (aChar == bChar) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int deleting = dp[i - 1][j];
                    int inserting = dp[i][j - 1];
                    int replacing = dp[i - 1][j - 1];
                    dp[i][j] = 1 + Math.min(Math.min(deleting, inserting), replacing);
                }
            }
        }
        return dp[aLength][bLength];
    }
}