Based on the code below, add a function to print the matix path: the result like

Question

Based on the code below, add a function to print the matix path:

the result like this

the original code:

#include

#include

int levenshtein(const char *s, const char *t)

{

int ls = strlen(s), lt = strlen(t);

int d[ls + 1][lt + 1];

int i,j;

for (i = 0; i <= ls; i++)

for (j = 0; j <= lt; j++)

d[i][j] = -1;

int dist(i,j) {

if (d[i][j] >= 0) return d[i][j];

int x;

if (i == ls)

x = lt - j;

else if (j == lt)

x = ls - i;

else if (s[i] == t[j])

x = dist(i + 1, j + 1);

else {

x = dist(i + 1, j + 1);

int y;

if ((y = dist(i, j + 1)) < x) x = y;

if ((y = dist(i + 1, j)) < x) x = y;

x++;

}

return d[i][j] = x;

}

return dist(0, 0);

}

int main(void)

{

const char *s1 = "cat";

const char *s2 = "cs";

printf("distance between `%s' and `%s': %d ", s1, s2,levenshtein(s1, s2));

return 0;

}

Explanation / Answer

Answer: See the code below:

------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int levenshtein(const char *s, const char *t)
{
   int ls = strlen(s), lt = strlen(t);
   int d[ls + 1][lt + 1];
   int i, j;
   for (i = 0; i <= ls; i++)
       for (j = 0; j <= lt; j++)
           d[i][j] = -1;
   int dist( i, j) {
       if (d[i][j] >= 0)
           return d[i][j];
       int x;
       if (i == ls)
           x = lt - j;
       else if (j == lt)
           x = ls - i;
       else if (s[i] == t[j])
           x = dist(i + 1, j + 1);
       else {
           x = dist(i + 1, j + 1);
           int y;
           if ((y = dist(i, j + 1)) < x)
               x = y;
           if ((y = dist(i + 1, j)) < x)
               x = y;
           x++;
       }
       return d[i][j] = x;
   }
   void print()
   {
       for (i = 0; i <= ls; i++){
           for (j = 0; j <= lt; j++)
               printf("| %d |",d[i][j]);
           printf(" ");
       }
   }
   print();
   return dist(0, 0);
}

int main(void)
{
   const char *s1 = "cat";
   const char *s2 = "cs";
   printf("distance between `%s' and `%s': %d ", s1, s2, levenshtein(s1, s2));
   return 0;
}

-------------------------------

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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