hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Delete Operation for Two Strings


  • Explanation:

This problem is a straightforward implication of the Longest Common Subsequence (LCS).

What is Longest Common Subsequence?

You have two strings. You will compare each of the characters of each string. You will have to make another string out of those two strings, where -

  • You have to keep the order the same for both strings. and

  • The formed string will be as long as possible.


For example, s1 = abcd and s2=adec. The LCS will be either ad or ac according to the mentioned condition above.

Now to find out LCS, we have to parse each of the characters of both strings from the beginning. Whenever we found a match on the ith and jth characters of s1 and s2, that is (s1[i] == s2[j]) we will increase the count by 1.


However, there is one "But". Will it be OK to just check the match? Can we get a string with maximum length?

The answer is No. Because the unmatched position will then have zero.

Let us assume, for the current state we have the maximized length. What we have to do is to propagate the maximized length so far of our current state to the next state through the unmatched position, so that we can use that maximized length when we have the match.

This way we can have the LCS. A classical Dynamic Programming problem.

You can find more of the Longest Common Subsequence in GeeksforGeeks. Check out.


Now to have the final answer for this problem -

  • we will reduce the length of s1 by the LCS length.

  • reduce the length of s2 by the LCS length.

  • the sum of the reduced length.


TaDa. Solved!


  • Time and Space Complexity: O(N^2)


Code [C++]

class Solution {

public:

int minDistance(string word1, string word2) {

int sz1 = word1.size(), sz2 = word2.size();

int table[sz1+1][sz2+1];

memset(table, 0, sizeof(table));

for(int i=1; i<=sz1; i++){

for(int j=1; j<=sz2; j++){

if(word1[i-1] == word2[j-1]){

table[i][j] = table[i-1][j-1] + 1;

}

else{

table[i][j] = max(table[i][j-1], table[i-1][j]);

}

}

}

return (sz1 + sz2 - 2*(table[sz1][sz2]));

}

};