583. Delete Operation for Two Strings
Description
Given two strings word1
and word2
, return the minimum number of steps required to make word1
and word2
the same.
In one step, you can delete exactly one character in either string.
Constraints
1 <= word1.length, word2.length <= 500
word1
andword2
consist of only lowercase English letters.
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Solutions
/**
* Time complexity : O(M*N), Where M is the size of the word1 and
* N is the size of the word2.
* Space complexity : O(M*N)
*/
class Solution {
public int minDistance(String word1, String word2) {
if(word1 == null && word2 == null) {
return 0;
} else if(word1 == null) {
return word2.length();
} else if(word2 == null) {
return word1.length();
}
int l1 = word1.length(), l2 = word2.length();
int[][] dp = new int[l1+1][l2+1];
for(int i = 0; i <= l1; i++) {
for(int j = 0; j <= l2; j++) {
if(i == 0 || j == 0) {
dp[i][j] = i + j;
} else if(word1.charAt(i-1) == word2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[l1][l2];
}
}
Follow up
Last updated
Was this helpful?