Repository: TheAlgorithms/Java
Pull request #5138 (2024-05-02 15:06:25)

Refactor Levenshtein distance implementation
## Changes
- Rewrite the original levenshtein distance implementation in functional style
- Add optimized version of levenshtein distance

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5138?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 37.37%. Comparing base [(`ede3e46`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ede3e4651f5443092427f6fdd12bf5bedcb5db0c?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`f513efe`)](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5138?dropdown=coverage&src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff            @@
##             master    #5138   +/-   ##
=========================================
  Coverage     37.36%   37.37%           
- Complexity     2350     2351    +1     
=========================================
  Files           517      517           
  Lines         15618    15614    -4     
  Branches       2971     2968    -3     
=========================================
  Hits           5836     5836           
+ Misses         9495     9491    -4     
  Partials        287      287           
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5138?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java b/src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java
index c4c9bbee..119d65df 100644
--- a/src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/LevenshteinDistance.java
@@ -1,49 +1,84 @@
 package com.thealgorithms.dynamicprogramming;
 
+import java.util.stream.IntStream;
+
 /**
- * @author Kshitij VERMA (github.com/kv19971) LEVENSHTEIN DISTANCE dyamic
- * programming implementation to show the difference between two strings
- * (https://en.wikipedia.org/wiki/Levenshtein_distance)
+ * 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 {
-
-    private static int minimum(int a, int b, int c) {
-        if (a < b && a < c) {
-            return a;
-        } else if (b < a && b < c) {
-            return b;
-        } else {
-            return c;
-        }
+public final class LevenshteinDistance {
+    private LevenshteinDistance() {
     }
 
-    public static int calculateLevenshteinDistance(String str1, String str2) {
-        int len1 = str1.length() + 1;
-        int len2 = str2.length() + 1;
-        int[][] distanceMat = new int[len1][len2];
-        for (int i = 0; i < len1; i++) {
-            distanceMat[i][0] = i;
-        }
-        for (int j = 0; j < len2; j++) {
-            distanceMat[0][j] = j;
+    /**
+     * 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`.
+     *
+     * 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();
         }
-        for (int i = 1; i < len1; i++) {
-            for (int j = 1; j < len2; j++) {
-                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
-                    distanceMat[i][j] = distanceMat[i - 1][j - 1];
-                } else {
-                    distanceMat[i][j] = 1 + minimum(distanceMat[i - 1][j], distanceMat[i - 1][j - 1], distanceMat[i][j - 1]);
-                }
+
+        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 distanceMat[len1 - 1][len2 - 1];
-    }
-
-    public static void main(String[] args) {
-        String str1 = ""; // enter your string here
-        String str2 = ""; // enter your string here
 
-        System.out.print("Levenshtein distance between " + str1 + " and " + str2 + " is: ");
-        System.out.println(calculateLevenshteinDistance(str1, str2));
+        return previousDistance[string1.length()];
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/LevenshteinDistanceTests.java b/src/test/java/com/thealgorithms/dynamicprogramming/LevenshteinDistanceTests.java
index a22bf3fe..ad4c4c7c 100644
--- a/src/test/java/com/thealgorithms/dynamicprogramming/LevenshteinDistanceTests.java
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/LevenshteinDistanceTests.java
@@ -2,15 +2,44 @@ package com.thealgorithms.dynamicprogramming;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
 
+import java.util.Arrays;
+import java.util.List;
+import java.util.function.ToIntBiFunction;
+import java.util.stream.Stream;
 import org.junit.jupiter.params.ParameterizedTest;
-import org.junit.jupiter.params.provider.CsvSource;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
 
 public class LevenshteinDistanceTests {
 
     @ParameterizedTest
-    @CsvSource({"dog,cat,3", "sunday,saturday,3", "cat,cats,1", "rain,train,1"})
-    void levenshteinDistanceTest(String str1, String str2, int distance) {
-        int result = LevenshteinDistance.calculateLevenshteinDistance(str1, str2);
-        assertEquals(distance, result);
+    @MethodSource("testCases")
+    public void testLevenshteinDistance(final int expected, final String str1, final String str2, final ToIntBiFunction<String, String> dist) {
+        assertEquals(expected, dist.applyAsInt(str1, str2));
+        assertEquals(expected, dist.applyAsInt(str2, str1));
+        assertEquals(0, dist.applyAsInt(str1, str1));
+        assertEquals(0, dist.applyAsInt(str2, str2));
+    }
+
+    private static Stream<Arguments> testCases() {
+        final Object[][] testData = {
+            {0, "", ""},
+            {0, "Hello, World!", "Hello, World!"},
+            {4, "", "Rust"},
+            {3, "horse", "ros"},
+            {6, "tan", "elephant"},
+            {8, "execute", "intention"},
+            {1, "a", "b"},
+            {1, "a", "aa"},
+            {1, "a", ""},
+            {1, "a", "ab"},
+            {1, "a", "ba"},
+            {2, "a", "bc"},
+            {2, "a", "cb"},
+        };
+
+        final List<ToIntBiFunction<String, String>> methods = Arrays.asList(LevenshteinDistance::naiveLevenshteinDistance, LevenshteinDistance::optimizedLevenshteinDistance);
+
+        return Stream.of(testData).flatMap(input -> methods.stream().map(method -> Arguments.of(input[0], input[1], input[2], method)));
     }
 }