Algorithms Question Given two strings X = x_1x_2...x_m and Y = y_1y_2...y_n, let

Question

Algorithms Question

Given two strings X = x_1x_2...x_m and Y = y_1y_2...y_n, let deleteScore (X, Y) be the least number of characters you have to delete from X, Y so that you get two same strings. For example, if X = goodman and Y = goldmann, then deleteScore(X, Y) = 3 (you can delete 'o' from X, '1' and one 'n' from Y to get the same string - "godman"). Give an algorithm that given two strings X, Y computes deletescore(X, Y). For full-credit, your algorithm should run in polynomial time. (Example: On input X = goodman, Y = goldmann your output should be 3.)

Explanation / Answer

// A Dynamic Programming based C++ program to find minimum
// number operations to convert str1 to str2
#include<iostream>
using namespace std;

// Utility function to find minimum of three numbers
int min(int x, int y)
{
   return x < y? x: y;
}

int editDistDP(string str1, string str2, int m, int n)
{
   // Create a table to store results of subproblems
   int dp[m+1][n+1];

   // Fill d[][] in bottom up manner
   for (int i=0; i<=m; i++)
   {
       for (int j=0; j<=n; j++)
       {
           if (i==0)
               dp[i][j] = j;

           else if (j==0)
               dp[i][j] = i;

           // If last characters are same, ignore last char
           // and recur for remaining string
           else if (str1[i-1] == str2[j-1])
               dp[i][j] = dp[i-1][j-1];

           // If last character are different, consider all
           // possibilities and find minimum
           else
               dp[i][j] = 1 + min(dp[i][j-1],
                               dp[i-1][j]);
       }
   }

   return dp[m][n];
}

int main()
{
   string str1 = "goodman";
   string str2 = "goldmann";

   cout << editDistDP(str1, str2, str1.length(), str2.length())<< endl;

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.