SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is to find the minimum number of operations required to convert one string into another. The allowed operations are:

1. Insert a character.
2. Delete a character.
3. Replace a character.

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

Intuition

The problem can be approached using dynamic programming (DP). We use a DP table to keep track of the minimum number of operations required to convert substrings of word1 to substrings of word2. By breaking the problem into smaller subproblems, we can solve it efficiently and avoid redundant computations using memoization.

Approach

1. Define the Recursive Function with Memoization:

   • Create a recursive function dp(i, j) that computes the minimum number of operations needed to convert word1[i:] to word2[j:].
   • Use a cache to store the results of subproblems and avoid redundant calculations.

2. Base Cases:

   • If i exceeds the length of word1, return the number of remaining characters in word2 from index j (all insert operations).
   • If j exceeds the length of word2, return the number of remaining characters in word1 from index i (all delete operations).

3. Recursive Cases:

   • If the characters word1[i] and word2[j] are equal, no operation is needed for these characters. Move to the next characters by calling dp(i + 1, j + 1).
   • If the characters are not equal, compute the cost of the three possible operations:
     • Insert: 1 + dp(i, j + 1)
     • Delete: 1 + dp(i + 1, j)
     • Replace: 1 + dp(i + 1, j + 1)
   • Store the minimum cost of these operations in the cache and return it.

4. Start the Recursion:

   • Start the recursion from the beginning of both strings by calling dp(0, 0).

5. Return the Result:

   • The result is the value returned by the initial call to dp(0, 0).

Complexity

Time Complexity:

O(m * n), where m is the length of word1 and n is the length of word2. Each subproblem is solved only once and stored in the cache.

Space Complexity:

O(m * n), for the cache that stores the results of subproblems

Code

C++

class Solution {
public:
    int minDistance(std::string word1, std::string word2) {
        std::unordered_map<std::string, int> cache;
        std::function<int(int, int)> dp = [&](int i, int j) -> int {
            std::string key = std::to_string(i) + "->" + std::to_string(j);
            if (cache.find(key) != cache.end()) {
                return cache[key];
            }
            if (i >= word1.length()) {
                return word2.length() - j;
            } 
            if (j >= word2.length()) {
                return word1.length() - i;
            }
            if (word1[i] == word2[j]) {
                return dp(i + 1, j + 1);
            }
            int insert = 1 + dp(i, j + 1);
            int del = 1 + dp(i + 1, j);
            int repl = 1 + dp(i + 1, j + 1);
            int res = std::min({insert, del, repl});
            cache[key] = res;
            return res;
        };
        return dp(0, 0);
    }
};

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        cache = {}
        def dp(i, j):
            if (i, j) in cache:
                return cache[(i, j)]
            if i >= len(word1):
                return len(word2) - j
            if j >= len(word2):
                return len(word1) - i
            if word1[i] == word2[j]:
                cache[(i, j)] = dp(i + 1, j + 1)
            else:
                insert = 1 + dp(i, j + 1)
                delete = 1 + dp(i + 1, j)
                replace = 1 + dp(i + 1, j + 1)
                cache[(i, j)] = min(insert, delete, replace)
            return cache[(i, j)]
        return dp(0, 0)

Java

class Solution {
    public int minDistance(String word1, String word2) {
        Map<String, Integer> cache = new HashMap<>();
        return dp(word1, word2, 0, 0, cache);
    }
    private int dp(String word1, String word2, int i, int j, Map<String, Integer> cache) {
        String key = i + "->" + j;
        if (cache.containsKey(key)) {
            return cache.get(key);
        }
        if (i >= word1.length()) {
            return word2.length() - j;
        } 
        if (j >= word2.length()) {
            return word1.length() - i;
        }
        if (word1.charAt(i) == word2.charAt(j)) {
            return dp(word1, word2, i + 1, j + 1, cache);
        }
        int insert = 1 + dp(word1, word2, i, j + 1, cache);
        int delete = 1 + dp(word1, word2, i + 1, j, cache);
        int replace = 1 + dp(word1, word2, i + 1, j + 1, cache);
        int res = Math.min(insert, Math.min(delete, replace));
        cache.put(key, res);
        return res;
    }
}

JavaScript

var minDistance = function(word1, word2) {
    const cache = {}
    function dp(i, j) {
        if (cache[`${i}->${j}`] !== undefined) {
            return cache[`${i}->${j}`]
        }
        if (i >= word1.length) {
            return word2.length - j;
        } 
        if (j >= word2.length) {
            return word1.length - i;
        }
        if (word1[i] === word2[j]) {
            return dp(i+1, j+1);
        }
        let insert = 1 + dp(i, j+1);
        let del = 1 + dp(i+1, j);
        let repl = 1 + dp(i+1, j+1);
        const res = Math.min(insert, del, repl);
        cache[`${i}->${j}`] = res;
        return res;
    }
    return dp(0, 0)
};