Write min_distance(word1: str, word2: str) -> int: the smallest number of single-character operations that turn word1 into word2. One operation is one of:
- insert a character anywhere,
- delete a character,
- replace a character with a different one.
Examples:
min_distance("cart", "chart") == 1(inserth)min_distance("sunday", "saturday") == 3min_distance("", "abc") == 3
Constraints: both words have at most 500 lowercase letters. Aim for O(m·n) time; the tests include two 500-letter words, so trying every sequence of edits will not finish.
Show hint
let dp[i][j] be the answer for the first i letters of word1 and the first j letters of word2.