Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Edit Distance

Hard · Dynamic Programming · Asked at Google, Amazon, Microsoft

Find the minimum number of operations to convert string a into string b. Allowed operations: insert, delete or replace one character.

Input

Two lines: string a and string b (lowercase letters).

Output

The minimum number of operations.

Constraints

Example 1

Input

horse
ros

Output

3

Example 2

Input

intention
execution

Output

5

Hints

  1. dp[i][j] = cost to turn the first i characters of a into the first j characters of b. dp[i][0] = i, dp[0][j] = j.
  2. If a[i−1] == b[j−1] no operation is needed: dp[i−1][j−1]. Otherwise 1 + min(replace dp[i−1][j−1], delete dp[i−1][j], insert dp[i][j−1]).

Approach

Levenshtein distance. Turning a prefix into the empty string takes i deletions, and building b's prefix from nothing takes j insertions. For other cells: if the last characters match, the cost is dp[i−1][j−1]. Otherwise do one operation and solve the smaller problem: replace (dp[i−1][j−1]), delete from a (dp[i−1][j]) or insert into a (dp[i][j−1]). Keeping two rows is enough.

Complexity: O(|a|·|b|) time · O(|b|) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<int> prev(m + 1), cur(m + 1);
    for (int j = 0; j <= m; j++) prev[j] = j;
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) cur[j] = prev[j - 1];
            else cur[j] = 1 + min(prev[j - 1], min(prev[j], cur[j - 1]));
        }
        swap(prev, cur);
    }
    cout << prev[m] << "\n";
    return 0;
}

Python solution

a = input().strip()
b = input().strip()
m = len(b)
prev = list(range(m + 1))
for i, ch in enumerate(a, 1):
    cur = [i] + [0] * m
    for j in range(1, m + 1):
        if ch == b[j - 1]:
            cur[j] = prev[j - 1]
        else:
            cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])
    prev = cur
print(prev[m])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next(), b = sc.next();
        int n = a.length(), m = b.length();
        int[] prev = new int[m + 1], cur = new int[m + 1];
        for (int j = 0; j <= m; j++) prev[j] = j;
        for (int i = 1; i <= n; i++) {
            cur[0] = i;
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) cur[j] = prev[j - 1];
                else cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
            }
            int[] t = prev; prev = cur; cur = t;
        }
        System.out.println(prev[m]);
    }
}

Solve Edit Distance online · All practice problems