Edit Distance

editDistance(S, T) computes the edit distance between two strings.

The allowed operations are insertion, deletion, and substitution of one character.

Import

import atcoder/extra/dp/edit_distance

Example

import atcoder/extra/dp/edit_distancedoAssert editDistance("kitten", "sitting") == 3doAssert editDistance("abc", "abc") == 0doAssert editDistance("abc", "") == 3

Complexity

Let S.len = n and T.len = m.

• Time: O(nm)
• Memory: O(m)