LCS || Leetcode 583. Delete Operation for Two Strings

Problem Link

In this problem , Given two strings. we have to make these two strings equal. In one move we can delete any character from either string. We have to do it in minimum number of steps possible.

Problem Idea: We have to reduce the strings, which makes the two strings equal. But hence we have to do it in minimum number of steps. So, we can say, we have to find such subsequence of strings that both the strings consisted. In other word we have to find the size of the longest common subsequence (LCS)

Complexity: O(m*n) ||   where m and n are size of the two strings.

Code[LCS Tabulization]:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: const static int sz = 505; int dp[sz][sz]; int lcs(string s1,string s2){ for(int i=0;i<s1.size();i++){ dp[i][0] = 0; } for(int i=0;i<s2.size();i++){ dp[0][i] = 0; } for(int i=1;i<=s1.size();i++){ for(int j=1;j<=s2.size();j++){ if(s1[i-1]==s2[j-1]){ dp[i][j] = dp[i-1][j-1]+1; }else{ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } return 2*dp[s1.size()][s2.size()]; } int minDistance(string word1, string word2) { return word1.size()+word2.size()-lcs(word1,word2); } };