Problem Statement

Given two strings source and target, return the minimum number of opreations required to convert source in to target.

You can perform the following three operations on a string:

• Insert a character
• Delete a character
• Replace a character

Example 1:

Input: source = "horse", target = "ros"
Output: 3
 horse -> rorse (replace 'h' with 'r')
 rorse -> rose (delete 'r')
 rose -> ros (delete 'e')

Example 2:

Input: source = "intention", target = "execution"
Output: 5
 intention -> inention (delete 't')
 inention -> enention (replace 'i' with 'e')
 enention -> exention (replace 'n' with 'x')
 exention -> exection (replace 'n' with 'c')
 exection -> execution (insert 'u')

Dynamic Programming Approach

State Definition

Create a 2D array dp where dp[i][j] represents the minimum operations needed to transform the first i characters of source into the first j characters of target.

Base Cases

When either string is empty:

• dp[i][0] = i: Converting i characters to an empty string requires i deletions
• dp[0][j] = j: Converting an empty string to j characters requires j insertions

Transition Formula

For each position (i, j), consider three possibilities:

1. Insert: dp[i][j-1] + 1 — Insert the j-th character of target
2. Delete: dp[i-1][j] + 1 — Delete the i-th character of source
3. Replace/Match: If source[i-1] == target[j-1], then dp[i-1][j-1]; otherwise dp[i-1][j-1] + 1

Take the minimum of all three approaches.

Implementation

public int minDistance(String source, String target) {
    int lenA = source.length();
    int lenB = target.length();
    
    if (lenA == 0) return lenB;
    if (lenB == 0) return lenA;
    
    int[][] dp = new int[lenA + 1][lenB + 1];
    
    for (int i = 0; i <= lenA; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= lenB; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            int insertCost = dp[i][j - 1] + 1;
            int deleteCost = dp[i - 1][j] + 1;
            int replaceCost = dp[i - 1][j - 1];
            
            if (source.charAt(i - 1) != target.charAt(j - 1)) {
                replaceCost++;
            }
            
            dp[i][j] = Math.min(insertCost, 
                       Math.min(deleteCost, replaceCost));
        }
    }
    
    return dp[lenA][lenB];
}

Complexity Analysis

• Time Complexity: O(m × n) where m and n are the lengths of the two strings
• Space Complexity: O(m × n) for the 2D DP array

Space-Optimized Version

Since each state only depends on the previous row, we can reduce space to O(n):

public int minDistance(String source, String target) {
    int lenA = source.length();
    int lenB = target.length();
    
    int[] prev = new int[lenB + 1];
    
    for (int j = 0; j <= lenB; j++) {
        prev[j] = j;
    }
    
    for (int i = 1; i <= lenA; i++) {
        int[] curr = new int[lenB + 1];
        curr[0] = i;
        
        for (int j = 1; j <= lenB; j++) {
            int insertCost = curr[j - 1] + 1;
            int deleteCost = prev[j] + 1;
            int replaceCost = prev[j - 1];
            
            if (source.charAt(i - 1) != target.charAt(j - 1)) {
                replaceCost++;
            }
            
            curr[j] = Math.min(insertCost, 
                      Math.min(deleteCost, replaceCost));
        }
        prev = curr;
    }
    
    return prev[lenB];
}

Key Insights

• The problem exhibits optimal substructure: the optimal solution for larger strings depends on optimal solutions for smaller prefixes
• Overlapping subproblems exist: the same (i, j) states are computed multiple times without optimizaton
• This is a classic example of bottom-up dynamic programming where we build solutions for larger problems from smaller ones