Edit Distance

Given two strings s1 and s2. Return the minimum number of operations required to convert s1 to s2.
The possible operations are permitted:

1. Insert a character at any position of the string.
2. Remove any character from the string.
3. Replace any character from the string with any other character.

Examples:

Input: s1 = "geek", s2 = "gesek"
Output: 1
Explanation: One operation is required, inserting 's' between two 'e' in s1.

Input: s1 = "gfg", s2 = "gfg"
Output: 0
Explanation: Both strings are same.

Input: s1 = "abcd", s2 = "bcfe"
Output: 3
Explanation: We can convert s1 into s2 by removing ‘a’, replacing ‘d’ with ‘f’ and inserting ‘e’ at the end. 

Constraints:
1 ≤ s1.length(), s2.length() ≤ 10³
Both the strings are in lowercase.

Approach 01:

#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
    int editDistance(std::string word1, std::string word2) {
        int length1 = word1.length(), length2 = word2.length();
        std::vector<std::vector<int>> dp(length1 + 1, std::vector<int>(length2 + 1));
        for (int i = 0; i <= length1; i++) {
            for (int j = 0; j <= length2; j++) {
                if (i == 0)
                    dp[i][j] = j; 
                else if (j == 0)
                    dp[i][j] = i; 
                else if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1]; 
                else
                    dp[i][j] = 1 + std::min({dp[i][j - 1],  
                                             dp[i - 1][j],  
                                             dp[i - 1][j - 1]}); 
            }
        }
        return dp[length1][length2];
    }
};

class Solution:
    def editDistance(self, word1: str, word2: str) -> int:
        length1, length2 = len(word1), len(word2)
        dp = [[None] * (length2 + 1) for _ in range(length1 + 1)]
        for i in range(length1 + 1):
            for j in range(length2 + 1):
                if i == 0:
                    dp[i][j] = j  
                elif j == 0:
                    dp[i][j] = i  
                elif word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]  
                else:
                    dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])  
        return dp[length1][length2]

Time Complexity:

• DP Table Filling:

  The algorithm iterates through a \( (m+1) \times (n+1) \) DP table, where \( m \) and \( n \) are the lengths of word1 and word2. Each cell is computed in constant time, leading to \( O(m \cdot n) \) complexity.

• Total Time Complexity:

  The overall time complexity is \( O(m \cdot n) \).

Space Complexity:

• DP Table Storage:

  The algorithm maintains a \( (m+1) \times (n+1) \) DP table, requiring \( O(m \cdot n) \) space.

• Other Variables:

  Only a few integer variables are used, contributing to \( O(1) \) space.

• Total Space Complexity:

  The overall space complexity is \( O(m \cdot n) \).