Edit Distance (Levenshtein Distance)

Reported in interviews at Citadel

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:

  1. s1 = "kitten", s2 = "sitting" -> 3
    • kitten -> sitten (substitute 'k' with 's')
    • sitten -> sittin (substitute 'e' with 'i')
    • sittin -> sitting (insert 'g' at end)
  1. s1 = "horse", s2 = "ros" -> 3
    • horse -> rorse (substitute 'h' with 'r')
    • rorse -> rose (delete 'r')
    • rose -> ros (delete 'e')
  1. 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.

Related free problems