Edit distance counts the minimum number of single-character insertions, deletions and
substitutions needed to turn one string into another. In molecular terms those three operations are
exactly indels and point mutations, which makes edit distance the simplest possible model of sequence
divergence. Every alignment algorithm you will meet later — Needleman-Wunsch, Smith-Waterman, the
banded aligners inside read mappers — is a weighted generalisation of this same dynamic programme.
Statement
Given two protein or DNA strings, compute their edit distance: the minimum number of
insertions, deletions and substitutions required to transform the first string into the second.
Print the distance as a single integer.
Input — read from standard input
| Variable | Type | Description |
|---|---|---|
s1
line 1
|
str |
The first string
1 <= len(s1) <= 1000
|
s2
line 2
|
str |
The second string
1 <= len(s2) <= 1000
|
These variables are already read for you in the starter code on the right.
Output
str a single integer, the minimum edit distance
Sample Cases
PLEASANTLY
MEANLY
5ACGT
ACGT
0Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.
Constraints
1 <= length(s1), length(s2) <= 1000- The two strings may have different lengths
- All three operations cost exactly 1
- Strings contain uppercase letters only
Further Reading
- Fill a
(len(s1)+1) x (len(s2)+1)table where cell(i, j)is the distance between prefixes. - The first row and column are the base cases: converting to or from an empty string costs its length.
- You only ever need the previous row, so a rolling one-dimensional array keeps memory at
O(min(n, m)).