Examveda

Consider the following implementation of the Wagner-Fischer algorithm:
int get_min(int a, int b)
{
     if(a < b)
        return a;
     return b;
}
int edit_distance(char *s1, char *s2)
{
     int len1,len2,i,j,min;
     len1 = strlen(s1);
     len2 = strlen(s2);
     int arr[len1 + 1][len2 + 1];
     for(i = 0;i <= len1; i++)
       arr[i][0] = i;
     for(i = 0; i <= len2; i++)
       arr[0][i] = i;
     for(i = 1; i <= len1; i++)
     {
         for(j = 1; j <= len2; j++)
         {
              min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
              if(s1[i - 1] == s2[j - 1])
              {
                  if(arr[i-1][j-1] < min)
                      ____________;
              }
              else
              {
                  if(arr[i-1][j-1] + 1 < min)
                      min = arr[i-1][j-1] + 1;
              }
              arr[i][j] = min;
         }
     }
     return arr[len1][len2];
}
Which of the following lines should be inserted to complete the above code?

A. arr[i][j] = min

B. min = arr[i-1][j-1] - 1;

C. min = arr[i-1][j-1].

D. min = arr[i-1][j-1] + 1;

Answer: Option C


Join The Discussion

Related Questions on Dynamic Programming in Data Structures