Edit Distance — Hard Coding Interview Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2 (Operations: Insert, Delete, Replace).

Example

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation: horse -> rorse -> rose -> ros

Constraints

• 0 ≤ word1.length, word2.length ≤ 500

Topics & Companies

Topics: dp

Asked by: Amazon, Google, Meta, Microsoft, Apple

Optimal Solution Complexity

Time complexity: O(m×n). Space complexity: O(n).

Practice more

• All DSA Problems
• DSA Patterns