#186MediumDynamic Programming· Two-String DP (Edit Distance)

Minimum Edits to Match

A spell-checker suggests corrections by measuring how many single-character edits are needed to turn what the user typed into a dictionary word. An edit is one of: - insert one character anywhere, - delete one character, - replace one character by another. Given the typed word `typed` and the dictionary word `target`, return the minimum number of edits that transforms `typed` into `target`. Either string may be empty.

Input format

`typed` and `target`: strings of lowercase English letters (possibly empty).

Output format

An integer: the minimum number of insertions, deletions and replacements.

Examples

Input: typed = "horse", target = "ros"

Output: 3

horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e): 3 edits.

Input: typed = "kitten", target = "sitting"

Output: 3

Replace k with s, replace e with i, and insert g: 3 edits.

Input: typed = "", target = "abc"

Output: 3

Building "abc" from nothing takes 3 insertions.

Constraints

0 <= typed.length, target.length <= 500
Both strings consist of lowercase English letters.

#dynamic-programming
#strings
#edit-distance