DSA · Dynamic Programming · #65

Edit Distance

Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given two strings `word1` and `word2`, return the minimum number of operations required to convert `word1` into `word2`. You may perform any of the following three operations on a string, each counting as one operation: - Insert a character - Delete a character - Replace a character Implement `minDistance(word1, word2)` returning the minimum edit (Levenshtein) distance as a number.

Examples

word1 = "horse", word2 = "ros" → 3 — horse -> rorse (replace 'h'->'r') -> rose (delete 'r') -> ros (delete 'e').
word1 = "intention", word2 = "execution" → 5 — Five operations transform one into the other.
word1 = "", word2 = "abc" → 3 — Insert three characters.

Constraints

· 0 <= word1.length, word2.length <= 500
· word1 and word2 consist of lowercase English letters.

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.