Practice/LinkedIn/Leetcode 72. Edit Distance

Leetcode 72. Edit Distance

CodingMust

Problem

Given two strings, determine the minimum number of operations required to transform the first string into the second string. You can perform three types of operations on a character:

• Insert a character at any position
• Delete a character from any position
• Replace a character with another character

Your task is to compute the smallest number of these operations needed to convert word1 into word2.

Requirements

1. Return the minimum number of operations as an integer
2. All three operations (insert, delete, replace) have equal cost of 1
3. Handle empty strings appropriately
4. The solution should work for any valid input strings

Constraints

• 0 <= word1.length, word2.length <= 500
• Both strings consist of lowercase English letters only
• Time complexity should be O(m × n) where m and n are the lengths of the two strings
• Space complexity can be optimized to O(min(m, n))

Examples

Example 1:

Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (delete 'r') rose -> ros (delete 'e') Total: 3 operations

Example 2:

Input: word1 = "saturday", word2 = "sunday" Output: 3 Explanation: saturday -> sturday (delete 'a') sturday -> sunday (replace 't' with 'n') sunday -> sunday (delete 'r') Total: 3 operations

Example 3:

Input: word1 = "", word2 = "a" Output: 1 Explanation: Insert character 'a'