Repository: TheAlgorithms/Java
File: src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java (Java)

Code before:
 * Provides functions to calculate the Levenshtein distance between two strings.
 *
 * The Levenshtein distance is a measure of the similarity between two strings by calculating the minimum number of single-character
 * edits (insertions, deletions, or substitutions) required to change one string into the other.
 */
public class LevenshteinDistance {

    /**
     * Calculates the Levenshtein distance between two strings using a naive dynamic programming approach.
     *
     * This function computes the Levenshtein distance by constructing a dynamic programming matrix and iteratively filling it in.
     * It follows the standard top-to-bottom, left-to-right approach for filling in the matrix.
     *
     * @param string1 The first string.
     * @param string2 The second string.
     * @return The Levenshtein distance between the two input strings.
     *
     * Time complexity: O(nm),
     * Space complexity: O(nm),
     *
     * where n and m are lengths of `string1` and `string2`.
     *
     * Note that this implementation uses a straightforward dynamic programming approach without any space optimization.
     * It may consume more memory for larger input strings compared to the optimized version.
     */
    public static int naiveLevenshteinDistance(String string1, String string2) {
        int[][] distanceMatrix = IntStream.rangeClosed(0, string1.length()).mapToObj(i -> IntStream.rangeClosed(0, string2.length()).map(j -> (i == 0) ? j : (j == 0) ? i : 0).toArray()).toArray(int[][] ::new);

        IntStream.range(1, string1.length() + 1).forEach(i -> IntStream.range(1, string2.length() + 1).forEach(j -> {
            int cost = (string1.charAt(i - 1) == string2.charAt(j - 1)) ? 0 : 1;
            distanceMatrix[i][j] = Math.min(distanceMatrix[i - 1][j - 1] + cost, Math.min(distanceMatrix[i][j - 1] + 1, distanceMatrix[i - 1][j] + 1));
        }));

        return distanceMatrix[string1.length()][string2.length()];
    }

    /**
     * Calculates the Levenshtein distance between two strings using an optimized dynamic programming approach.
     *
     * This edit distance is defined as 1 point per insertion, substitution, or deletion required to make the strings equal.
     *
     * @param string1 The first string.
     * @param string2 The second string.
     * @return The Levenshtein distance between the two input strings.
     *
     * Time complexity: O(nm),
     * Space complexity: O(n),
     *
     * where n and m are lengths of `string1` and `string2`.
     *
     * Note that this implementation utilizes an optimized dynamic programming approach, significantly reducing the space complexity from O(nm) to O(n), where n and m are the lengths of `string1` and `string2`.

Review comment (suggestion):
```suggestion
    public static int naiveLevenshteinDistance(final String string1, final String string2) {
```

Code after:
 * Provides functions to calculate the Levenshtein distance between two strings.
 *
 * The Levenshtein distance is a measure of the similarity between two strings by calculating the minimum number of single-character
 * edits (insertions, deletions, or substitutions) required to change one string into the other.
 */
public final class LevenshteinDistance {
    private LevenshteinDistance() {
    }

    /**
     * Calculates the Levenshtein distance between two strings using a naive dynamic programming approach.
     *
     * This function computes the Levenshtein distance by constructing a dynamic programming matrix and iteratively filling it in.
     * It follows the standard top-to-bottom, left-to-right approach for filling in the matrix.
     *
     * @param string1 The first string.
     * @param string2 The second string.
     * @return The Levenshtein distance between the two input strings.
     *
     * Time complexity: O(nm),
     * Space complexity: O(nm),
     *
     * where n and m are lengths of `string1` and `string2`.
     *
     * Note that this implementation uses a straightforward dynamic programming approach without any space optimization.
     * It may consume more memory for larger input strings compared to the optimized version.
     */
    public static int naiveLevenshteinDistance(final String string1, final String string2) {
        int[][] distanceMatrix = IntStream.rangeClosed(0, string1.length()).mapToObj(i -> IntStream.rangeClosed(0, string2.length()).map(j -> (i == 0) ? j : (j == 0) ? i : 0).toArray()).toArray(int[][] ::new);

        IntStream.range(1, string1.length() + 1).forEach(i -> IntStream.range(1, string2.length() + 1).forEach(j -> {
            final int cost = (string1.charAt(i - 1) == string2.charAt(j - 1)) ? 0 : 1;
            distanceMatrix[i][j] = Math.min(distanceMatrix[i - 1][j - 1] + cost, Math.min(distanceMatrix[i][j - 1] + 1, distanceMatrix[i - 1][j] + 1));
        }));

        return distanceMatrix[string1.length()][string2.length()];
    }

    /**
     * Calculates the Levenshtein distance between two strings using an optimized dynamic programming approach.
     *
     * This edit distance is defined as 1 point per insertion, substitution, or deletion required to make the strings equal.
     *
     * @param string1 The first string.
     * @param string2 The second string.
     * @return The Levenshtein distance between the two input strings.
     *
     * Time complexity: O(nm),
     * Space complexity: O(n),
     *
     * where n and m are lengths of `string1` and `string2`.