Loading problem…
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Operations: Insert, Delete, Replace a character.
Example 1
Input: word1 = horse, word2 = ros
Output: 3
Explanation: horse → rorse (replace 'h' with 'r'), rorse → rose (delete 'r'), rose → ros (delete 'e'). That is 3 operations, and no shorter sequence works.
Example 2
Input: word1 = intention, word2 = execution
Output: 5
Explanation: intention → inention (delete 't'), → enention (replace 'i' with 'e'), → exention (replace 'n' with 'x'), → exection (replace 'n' with 'c'), → execution (insert 'u'). That is 5 operations.
Example 3
Input: word1 = , word2 =
Output: 0
Explanation: Both strings are empty, so no operations are needed.
The 2D DP only ever reads from `dp[i-1][...]` (the row above) and `dp[i][j-1]` (the cell to the left). Keep just two rows around — the previous one and the one we're filling — and we drop space from `O(m · n)` to `O(n)`.
Run checks all cases above. Submit evaluates all test cases.