Given two strings str1 and str2. Return the minimum number of operations required to convert str1 to str2.
The possible operations are permitted:
- Insert a character at any position of the string.
- Remove any character from the string.
- Replace any character from the string with any other character.
Examples:
Input: str1 = "geek", srt2 = "gesek" Output: 1 Explanation: One operation is required, inserting 's' between two 'e'.
Input : str1 = "gfg", str2 = "gfg" Output: 0 Explanation: Both strings are same.
Expected Time Complexity: O(|str1|*|str2|)
Expected Space Complexity: O(|str1|*|str2|)
Constraints:
1 ≤ str1.length(), str2.length() ≤ 100
Both the strings are in lowercase.
Approach 01:
-
C++
-
Python
#include <vector>
#include <string>
#include <climits>
using namespace std;
class Solution {
public:
// Helper function to calculate the minimum edit distance
int calculateEditDistance(string &str1, string &str2, int len1, int len2, vector<vector<int>>& dp) {
// Base cases: if one string is empty, the edit distance is the length of the other string
if (len1 == -1)
return len2 + 1;
if (len2 == -1)
return len1 + 1;
// If the result is already computed, return it
if (dp[len1][len2] != INT_MAX)
return dp[len1][len2];
// If the characters match, no edit is needed for this character
if (str1[len1] == str2[len2]) {
return dp[len1][len2] = min(dp[len1][len2], calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp));
}
// Calculate the minimum of inserting, deleting, or replacing a character
dp[len1][len2] = min(dp[len1][len2], 1 + calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp)); // Replace
dp[len1][len2] = min(dp[len1][len2], 1 + calculateEditDistance(str1, str2, len1 - 1, len2, dp)); // Delete
dp[len1][len2] = min(dp[len1][len2], 1 + calculateEditDistance(str1, str2, len1, len2 - 1, dp)); // Insert
return dp[len1][len2];
}
int editDistance(string str1, string str2) {
int len1 = str1.length();
int len2 = str2.length();
vector<vector<int>> dp(len1, vector<int>(len2, INT_MAX)); // DP table to store results
return calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp); // Start from the end of both strings
}
};
from typing import List
class Solution:
# Helper function to calculate the minimum edit distance
def calculateEditDistance(self, str1: str, str2: str, len1: int, len2: int, dp: List[List[int]]) -> int:
# Base cases: if one string is empty, the edit distance is the length of the other string
if len1 == -1:
return len2 + 1
if len2 == -1:
return len1 + 1
# If the result is already computed, return it
if dp[len1][len2] != float('inf'):
return dp[len1][len2]
# If the characters match, no edit is needed for this character
if str1[len1] == str2[len2]:
dp[len1][len2] = min(dp[len1][len2], self.calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp))
return dp[len1][len2]
# Calculate the minimum of inserting, deleting, or replacing a character
dp[len1][len2] = min(dp[len1][len2], 1 + self.calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp)) # Replace
dp[len1][len2] = min(dp[len1][len2], 1 + self.calculateEditDistance(str1, str2, len1 - 1, len2, dp)) # Delete
dp[len1][len2] = min(dp[len1][len2], 1 + self.calculateEditDistance(str1, str2, len1, len2 - 1, dp)) # Insert
return dp[len1][len2]
def editDistance(self, str1: str, str2: str) -> int:
len1 = len(str1)
len2 = len(str2)
dp = [[float('inf')] * len2 for _ in range(len1)] # DP table to store results
return self.calculateEditDistance(str1, str2, len1 - 1, len2 - 1, dp) # Start from the end of both strings
Time Complexity
- Recursive Calls:
The recursive function
calculateEditDistanceis called with all possible combinations of lengths of the two strings, resulting in \( O(m \cdot n) \) calls, where \( m \) and \( n \) are the lengths ofstr1andstr2, respectively. - Memoization:
Since each state is computed only once and then stored in the
dptable, the time complexity for each state is \( O(1) \). Therefore, the overall time complexity is \( O(m \cdot n) \).
Space Complexity
- Auxiliary Space:
The recursive function uses stack space proportional to the maximum depth of recursion, which is \( O(m + n) \). However, this can be considered part of the overall space complexity.
- DP Table:
The
dptable has dimensions \( m \times n \), resulting in \( O(m \cdot n) \) space complexity for storing the intermediate results. - Overall Space Complexity:
The overall space complexity is \( O(m \cdot n) \) due to the
dptable.