Edit Distance - Practice Coding Problems

Edit Distance - Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

This problem is also known as the Levenshtein Distance.

Input & Output

Example 1 — Basic Transformation

$ Input: word1 = "horse", word2 = "ros"

› Output: 3

💡 Note: horse → rorse (replace 'h' with 'r') → rose (remove 'r') → ros (remove 'e'). Total: 3 operations.

Example 2 — Insert Operations

$ Input: word1 = "intention", word2 = "execution"

› Output: 5

💡 Note: intention → inention (delete 't') → enention (replace 'i' with 'e') → exention (replace first 'n' with 'x') → exection (replace 'n' with 'c') → execution (insert 'u'). Total: 5 operations.

Example 3 — Edge Case Empty String

$ Input: word1 = "abc", word2 = ""

› Output: 3

💡 Note: Delete all 3 characters from 'abc' to get empty string. Total: 3 operations.

Constraints

0 ≤ word1.length, word2.length ≤ 500
word1 and word2 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

Compare characters from both strings

Apply Operations

Use insert, delete, or replace operations

Minimum Cost

Find path with minimum total operations

Key Takeaway

🎯 Key Insight: Each position in the DP table represents the minimum cost to transform a prefix of word1 into a prefix of word2

Asked in

G Google 45 f Facebook 38 M Microsoft 32 a Amazon 28

The key insight is recognizing this as a classic dynamic programming problem where each position depends on three possible operations. The optimal approach uses a 2D DP table to build solutions bottom-up. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(m×n)	O(m×n)	Build a 2D table bottom-up to find minimum operations
Recursive with Memoization	O(m×n)	O(m×n)	Add caching to avoid recalculating same subproblems
Recursive Brute Force	O(3^(m+n))	O(m+n)	Try all possible operations recursively without memoization

2D Dynamic Programming — Algorithm Steps

Initialize DP table with base cases
For each cell, consider three operations
Choose minimum cost operation
Return dp[m][n] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Base Cases

Fill first row and column

Fill Table

Each cell depends on three neighbors

Get Answer

Bottom-right cell contains result

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(const char* word1, const char* word2) {
    int m = strlen(word1), n = strlen(word2);
    int** dp = (int**)malloc((m + 1) * sizeof(int*));
    for (int i = 0; i <= m; i++) {
        dp[i] = (int*)malloc((n + 1) * sizeof(int));
    }
    
    // Base cases
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    
    // Fill DP table
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i-1] == word2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + min(
                    min(dp[i-1][j], dp[i][j-1]),
                    dp[i-1][j-1]
                );
            }
        }
    }
    
    int result = dp[m][n];
    
    // Free memory
    for (int i = 0; i <= m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    char word1[1000], word2[1000];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    printf("%d\n", solution(word1, word2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Double loop iterates through all m×n table entries

✓ Linear Growth

Space Complexity

O(m×n)

2D DP table stores (m+1)×(n+1) values

⚡ Linearithmic Space

425.0K Views

High Frequency

~25 min Avg. Time

8.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler