String Transformation Cost - Minimum Edit Distance with Dynamic Programming

Given two strings word1 and word2, find the minimum number of operations needed to transform word1 into word2. You can insert a character, delete a character, or replace a character, and each operation costs exactly 1. This problem is also known as Edit Distance on other platforms and is one of the most frequently asked dynamic programming questions at companies like Google, Adobe, Apple, and Amazon.

For example, transforming "horse" into "ros" requires 3 operations: replace h with r, remove the second r, and remove e. The challenge is finding the sequence that uses the fewest operations possible.

Understanding the Three Operations

Before jumping into the algorithm, let's be precise about what each operation does.

Insert adds a character at any position in word1. Delete removes a character from word1. Replace swaps one character in word1 for a different one. Each costs 1 regardless of position or character.

The goal is to find the combination of these operations that minimizes the total cost. A greedy approach (scanning left to right) fails because an early replacement might save deletions later. We need to consider all possible sequences, and that is where dynamic programming comes in.

Building the DP Table

Define dp[i][j] as the minimum operations to convert the first i characters of word1 into the first j characters of word2. The final answer lives at dp[m][n] where m and n are the string lengths.

Prefer a different language? Jump to solutions in other languages.

Base Cases

When one string is empty, the answer is straightforward:

• dp[0][j] = j for all j: transforming an empty string into word2[0..j] requires j insertions
• dp[i][0] = i for all i: transforming word1[0..i] into an empty string requires i deletions

The Recurrence

For every cell dp[i][j], compare word1[i-1] and word2[j-1]:

• Characters match: No operation needed. dp[i][j] = dp[i-1][j-1].
• Characters differ: Take the minimum of three options, plus 1:
  • dp[i-1][j-1] + 1 (replace)
  • dp[i-1][j] + 1 (delete from word1)
  • dp[i][j-1] + 1 (insert into word1)

The diagonal cell dp[i-1][j-1] represents replacing the mismatched character. The cell above dp[i-1][j] represents deleting from word1 (we've consumed a character of word1 without matching). The cell to the left dp[i][j-1] represents inserting into word1 (we've matched a character of word2 by adding it).

Interactive DP Table: "sat" to "sun"

Watch the table fill step by step for transforming "sat" into "sun". Use the controls to pause and step through at your own pace. Pay attention to how each cell references its neighbors.

The final cell shows 2, meaning two operations: replace a with u and replace t with n. The first characters already match (s = s), so that cell inherits 0 from the diagonal.

Walkthrough: "horse" to "ros"

Let's trace through a larger example. The DP table for "horse" and "ros" produces 3, and the transformation follows this path:

Replace h with r to get "rorse", delete the second r to get "rose", then delete e to get "ros". Three operations total. Other sequences of three operations exist, but none can do it in fewer.

Java Implementation

public class Solution {

  public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i == 0) {
          dp[i][j] = j;
        } else if (j == 0) {
          dp[i][j] = i;
        } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                         Math.min(dp[i - 1][j], dp[i][j - 1]));
        }
      }
    }

    return dp[m][n];
  }
}

The structure is compact. Initialization and computation happen in the same loop by checking whether i or j is zero. When both are positive and the characters match, we skip the operation cost entirely.

Complexity Analysis

Time: O(m * n) where m = word1.length() and n = word2.length(). We fill every cell in the (m+1) x (n+1) table once, and each cell takes constant work.

Space: O(m * n) for the DP table. You can reduce this to O(min(m, n)) by observing that each row only depends on the previous row. Keep two rows and alternate between them, or use a single row with a temporary variable tracking the diagonal value.

Edge Cases to Consider

• Both strings empty: dp[0][0] = 0. No operations needed.
• One string empty: The answer is the length of the non-empty string (all inserts or all deletes).
• Identical strings: Every character matches, so the diagonal values propagate through and the answer is 0.
• Completely different strings of equal length: The answer is at most n (replace every character), but could be less if some prefix/suffix overlap helps.
• One string is a substring of the other: The difference in lengths gives the minimum (all inserts or deletes).

Practice This Problem

String Transformation Cost is a pillar of dynamic programming interviews. The recurrence is clean, but filling the table correctly under pressure requires practice. Try it yourself on Firecode.io where you can step through hints and test against 12 edge cases.

If you found this problem approachable, try these related problems next:

• Sentence Formation with Word Dictionary (backtracking + memoization on strings)
• Step Combinations to Reach the Summit (1D DP with similar recurrence thinking)
• Count Paths on a Board (2D DP on a grid, same table-filling pattern)

Solutions in Other Languages

Python

class Solution:
    def min_distance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j],
                                       dp[i][j - 1],
                                       dp[i - 1][j - 1])

        return dp[m][n]

JavaScript

class Solution {
  minDistance(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) {
      dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
      dp[0][j] = j;
    }

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (word1[i - 1] === word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = Math.min(
            dp[i - 1][j] + 1,
            dp[i][j - 1] + 1,
            dp[i - 1][j - 1] + 1
          );
        }
      }
    }

    return dp[m][n];
  }
}

TypeScript

class Solution {
  minDistance(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () =>
      Array(n + 1).fill(0)
    );

    for (let i = 0; i <= m; i++) {
      dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
      dp[0][j] = j;
    }

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (word1[i - 1] === word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = Math.min(
            dp[i - 1][j] + 1,
            dp[i][j - 1] + 1,
            dp[i - 1][j - 1] + 1
          );
        }
      }
    }

    return dp[m][n];
  }
}

C++

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
  int minDistance(std::string &word1, std::string &word2) {
    int m = word1.size();
    int n = word2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 0; i <= m; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (i == 0) {
          dp[i][j] = j;
        } else if (j == 0) {
          dp[i][j] = i;
        } else if (word1[i - 1] == word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1],
                                    dp[i - 1][j - 1]});
        }
      }
    }

    return dp[m][n];
  }
};

Go

func MinDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }

    return dp[m][n]
}

func min(a, b, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

Scala

class Solution {
  def minDistance(word1: String, word2: String): Int = {
    val m = word1.length
    val n = word2.length
    val dp = Array.ofDim[Int](m + 1, n + 1)

    for (i <- 0 to m) {
      for (j <- 0 to n) {
        if (i == 0) {
          dp(i)(j) = j
        } else if (j == 0) {
          dp(i)(j) = i
        } else if (word1(i - 1) == word2(j - 1)) {
          dp(i)(j) = dp(i - 1)(j - 1)
        } else {
          dp(i)(j) = 1 + math.min(dp(i - 1)(j - 1),
                         math.min(dp(i - 1)(j), dp(i)(j - 1)))
        }
      }
    }

    dp(m)(n)
  }
}

Kotlin

class Solution {
  fun minDistance(word1: String, word2: String): Int {
    val m = word1.length
    val n = word2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    for (i in 0..m) {
      for (j in 0..n) {
        if (i == 0) {
          dp[i][j] = j
        } else if (j == 0) {
          dp[i][j] = i
        } else if (word1[i - 1] == word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1]
        } else {
          dp[i][j] = 1 + minOf(dp[i - 1][j - 1],
                        minOf(dp[i - 1][j], dp[i][j - 1]))
        }
      }
    }

    return dp[m][n]
  }
}

Swift

class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        let chars1 = Array(word1)
        let chars2 = Array(word2)
        let m = chars1.count
        let n = chars2.count
        var dp = Array(repeating: Array(repeating: 0, count: n + 1),
                       count: m + 1)

        for i in 0...m {
            for j in 0...n {
                if i == 0 {
                    dp[i][j] = j
                } else if j == 0 {
                    dp[i][j] = i
                } else if chars1[i - 1] == chars2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1]
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],
                                   min(dp[i - 1][j], dp[i][j - 1]))
                }
            }
        }

        return dp[m][n]
    }
}

Rust

impl Solution {
    pub fn min_distance(&self, word1: String, word2: String) -> i32 {
        let m = word1.len();
        let n = word2.len();
        let word1_bytes = word1.as_bytes();
        let word2_bytes = word2.as_bytes();
        let mut dp = vec![vec![0; n + 1]; m + 1];

        for i in 0..=m {
            for j in 0..=n {
                if i == 0 {
                    dp[i][j] = j as i32;
                } else if j == 0 {
                    dp[i][j] = i as i32;
                } else if word1_bytes[i - 1] == word2_bytes[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                        .min(dp[i - 1][j])
                        .min(dp[i][j - 1]);
                }
            }
        }

        dp[m][n]
    }
}

C#

public class Solution {
    public int minDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        var dp = new int[m + 1, n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i, j] = j;
                } else if (j == 0) {
                    dp[i, j] = i;
                } else if (word1[i - 1] == word2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1];
                } else {
                    dp[i, j] = 1 + Math.Min(dp[i - 1, j - 1],
                                   Math.Min(dp[i - 1, j], dp[i, j - 1]));
                }
            }
        }

        return dp[m, n];
    }
}

Dart

import 'dart:math';

class Solution {
  int minDistance(String word1, String word2) {
    int m = word1.length;
    int n = word2.length;
    List<List<int>> dp =
        List.generate(m + 1, (_) => List.filled(n + 1, 0));

    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (i == 0) {
          dp[i][j] = j;
        } else if (j == 0) {
          dp[i][j] = i;
        } else if (word1[i - 1] == word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + min(dp[i - 1][j - 1],
                       min(dp[i - 1][j], dp[i][j - 1]));
        }
      }
    }

    return dp[m][n];
  }
}

PHP

class Solution {
    public function minDistance(string $word1, string $word2): int {
        $m = strlen($word1);
        $n = strlen($word2);
        $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

        for ($i = 0; $i <= $m; $i++) {
            for ($j = 0; $j <= $n; $j++) {
                if ($i == 0) {
                    $dp[$i][$j] = $j;
                } elseif ($j == 0) {
                    $dp[$i][$j] = $i;
                } elseif ($word1[$i - 1] == $word2[$j - 1]) {
                    $dp[$i][$j] = $dp[$i - 1][$j - 1];
                } else {
                    $dp[$i][$j] = 1 + min($dp[$i - 1][$j - 1],
                                     $dp[$i - 1][$j], $dp[$i][$j - 1]);
                }
            }
        }

        return $dp[$m][$n];
    }
}

Ruby

class Solution
  def min_distance(word1, word2)
    m = word1.length
    n = word2.length
    dp = Array.new(m + 1) { Array.new(n + 1, 0) }

    (0..m).each do |i|
      (0..n).each do |j|
        if i == 0
          dp[i][j] = j
        elsif j == 0
          dp[i][j] = i
        elsif word1[i - 1] == word2[j - 1]
          dp[i][j] = dp[i - 1][j - 1]
        else
          dp[i][j] = 1 + [dp[i - 1][j - 1], dp[i - 1][j],
                           dp[i][j - 1]].min
        end
      end
    end

    dp[m][n]
  end
end