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

Code before:
     * @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`.
     *
     * Additionally, it minimizes space usage by leveraging the shortest string horizontally and the longest string vertically in the computation matrix.
     */
    public static int optimizedLevenshteinDistance(String string1, String string2) {
        if (string1.isEmpty()) {
            return string2.length();
        }

        int[] previousDistance = IntStream.rangeClosed(0, string1.length()).toArray();

        for (int j = 1; j <= string2.length(); j++) {
            int prevSubstitutionCost = previousDistance[0];
            previousDistance[0] = j;

            for (int i = 1; i <= string1.length(); i++) {
                int deletionCost = previousDistance[i] + 1;
                int insertionCost = previousDistance[i - 1] + 1;
                int substitutionCost = (string1.charAt(i - 1) == string2.charAt(j - 1)) ? prevSubstitutionCost : prevSubstitutionCost + 1;
                prevSubstitutionCost = previousDistance[i];
                previousDistance[i] = Math.min(deletionCost, Math.min(insertionCost, substitutionCost));
            }
        }

        return previousDistance[string1.length()];
    }
}


Review comment (suggestion):
```suggestion
                final int deletionCost = previousDistance[i] + 1;
                final int insertionCost = previousDistance[i - 1] + 1;
                final int substitutionCost = (string1.charAt(i - 1) == string2.charAt(j - 1)) ? prevSubstitutionCost : prevSubstitutionCost + 1;
```

Code after:
     * @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`.
     *
     * Additionally, it minimizes space usage by leveraging the shortest string horizontally and the longest string vertically in the computation matrix.
     */
    public static int optimizedLevenshteinDistance(final String string1, final String string2) {
        if (string1.isEmpty()) {
            return string2.length();
        }

        int[] previousDistance = IntStream.rangeClosed(0, string1.length()).toArray();

        for (int j = 1; j <= string2.length(); j++) {
            int prevSubstitutionCost = previousDistance[0];
            previousDistance[0] = j;

            for (int i = 1; i <= string1.length(); i++) {
                final int deletionCost = previousDistance[i] + 1;
                final int insertionCost = previousDistance[i - 1] + 1;
                final int substitutionCost = (string1.charAt(i - 1) == string2.charAt(j - 1)) ? prevSubstitutionCost : prevSubstitutionCost + 1;
                prevSubstitutionCost = previousDistance[i];
                previousDistance[i] = Math.min(deletionCost, Math.min(insertionCost, substitutionCost));
            }
        }

        return previousDistance[string1.length()];
    }
}