Edit Distance (Levenshtein) in Java: Explanation & Practice

Minimum operations to convert one string to another

Problem summary

Given two strings, find the minimum number of operations (insert, delete, replace) to convert word1 to word2. Classic DP problem!

Starter code

public class Main {
    public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        
        // dp[i][j] = min ops to convert word1[0..i-1] to word2[0..j-1]
        // If match: dp[i-1][j-1]
        // Else: 1 + min(insert, delete, replace)
        // Print: Distance: 3
    }
}

Expected output and test cases

horse → ros: 3 ops
```
Distance: 3
```
intention → execution: 5 ops
```
Distance: 5
```
abc → def: 3 replaces
```
Distance: 3
```

Hints

dp[i][j] = min operations for word1[0..i-1] → word2[0..j-1]
Base: dp[i][0]=i (delete all), dp[0][j]=j (insert all)
If chars match: dp[i][j] = dp[i-1][j-1] (no operation needed)
Else: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler