Edit Distance (Levenshtein Distance)
Problem statement
You are given two strings $s_1$ and $s_2$. You can transform $s_1$ into $s_2$ using three operations, each costing 1:
- Insert a character at any position
- Delete a character at any position
- Substitute one character for another
Write a function that returns the minimum total number of operations needed to convert $s_1$ into $s_2$. This quantity is known as the Levenshtein (edit) distance.
Constraints:
- $0 \leq |s_1|, |s_2| \leq 500$
- Both strings consist of lowercase English letters
Examples:
s1 = "kitten",s2 = "sitting"->3- kitten -> sitten (substitute 'k' with 's')
- sitten -> sittin (substitute 'e' with 'i')
- sittin -> sitting (insert 'g' at end)
s1 = "horse",s2 = "ros"->3- horse -> rorse (substitute 'h' with 'r')
- rorse -> rose (delete 'r')
- rose -> ros (delete 'e')
s1 = "",s2 = "abc"->3(3 insertions)
Show hint
What smaller version of the same question could you answer if you only considered the first few characters of each string?
Relevant roles: ML Engineer, AI Engineer, LLM Engineer and Forward Deployed Engineer.