72. Edit Distance

Problem Statement

link: LeetCode.cn LeetCode

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character Delete a character Replace a character

Example:

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

Input: word1 = "intention", word2 = "execution" Output: 5

Solution Approach

The problem is solved using dynamic programming where each entry in a 2D table represents the minimum number of edits needed to convert a prefix of word1 to a prefix of word2.

Algorithm

1. Initialization: Create a 2D table dp where dp[i][j] indicates edits to convert the first i characters of word1 to j characters of word2.
2. Population: If characters match, dp[i][j] = dp[i-1][j-1]. If not, factor in the cost of insertions, deletions, or replacements.
3. Result: The value dp[len(word1)][len(word2)] gives the minimum operations to convert word1 to word2.

Implement

    class Solution:
      def minDistance(self, word1: str, word2: str) -> int:
        l1, l2 = len(word1), len(word2)
        steps1 = [i for i in range(l1 + 1)]
        steps2 = [0] * (l1 + 1)
        for i in range(1, l2 + 1):
            steps2[0] = i
            for j in range(1, l1 + 1):
                if word2[i - 1] == word1[j - 1]:
                    steps2[j] = steps1[j - 1]
                else:
                    steps2[j] = min(steps1[j - 1], steps2[j - 1], steps1[j]) + 1
            steps1 = steps2[:]
        return steps1[-1]
 

    
    

Twitter  facebook  Email