Edit Distance Problem: 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 Explanation: horse -> rorse (replace 'h' with 'r')
Table of Contents
Edit Distance Problem Solution
Problem Solution In Python
class Solution:
def minDistance(self, A: str, B: str) -> int:
if not A: return len(B)
if not B: return len(A)
m, n = len(A), len(B)
dp = [[-1] * (n+1) for _ in range(m+1)]
dp[0][0] = 0
for i in range(1, m+1):
dp[i][0] = i
for j in range(1, n+1):
dp[0][j] = j
dp[i][j] = min(
dp[i-1][j]+1,
dp[i][j-1]+1,
dp[i-1][j-1]+(A[i-1]!=B[j-1])
)
return dp[-1][-1]
Problem Solution In Java
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m+1][n+1];
for(int i=0; i<=m; i++) dp[i][0] = i;
for(int j=0; j<=n; j++) dp[0][j] = j;
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(word1.charAt(i-1) == word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
}
}
return dp[m][n];
}
}
Problem Solution In C++
class Solution {
public:
int minDistance(string word1, string word2) {
int n=word1.length();
int m=word2.length();
int dp[n+5][m+5];
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i][0]=i;
}
for(int i=0;i<=m;i++)
{
dp[0][i]=i;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(word1[i-1]==word2[j-1])
{
dp[i][j]=min({dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1});
}
else
{
dp[i][j]=min({dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1});
}
}
}
return dp[n][m];
}
};
Problem Solution In C
int minDistance(char * word1, char * word2){
int m = strlen(word2);
char *s1 = word1;
char *s2 = word2;
int *mat = malloc(sizeof(int) * (m+1));
for(int i=0; i<=m; ++i) {
mat[i] = i;
}
for(int i=1; *s1; ++i, ++s1) {
s2 = word2;
int pre = i-1;
mat[0] = i;
for(int j=1; j<=m; ++s2, ++j) {
int tmp = mat[j];
int min = *s2 == *s1 ? pre : pre+1;
min = min < mat[j-1]+1 ? min : mat[j-1]+1;
mat[j] = mat[j]+1 < min ? mat[j]+1 : min;
pre = tmp;
}
}
return mat[m];
}