Edit Distance (DP)

Problem

Given two strings, compute the minimum number of insert/delete/replace operations to transform one into the other.

Input

Two lines: string a, string b.

Output

Minimum edit distance.

Constraints

0 ≤ |a|, |b| ≤ 1000

Sample input

horse
ros

Sample output

Explanation

horse → rorse (replace h→r) → rose (remove r) → ros (remove e). 3 ops.

dpstrings@Google@Amazon@Apple

Visible test cases

in: horse
ros

out: 3

in: intention
execution

out: 5

Your solution — run it, use AI if stuck

cpp