Home / MCQ Bank / Computer
Computer Dynamic Programming In Data Structures Difficulty: Medium

What is the space complexity of the following dynamic programming implementation of the edit distance problem where "m" and "n" are the lengths of the two strings? #include<stdio.h> #include<string.h> 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) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }

Select the correct option to test your answer:

More Computer Questions

What are the small squares arranged in rows and columns called in Excel? In Excel which key is used to select entire column? In time series analysis, what does the "autocorrelation function" (ACF) measure? Which of these keywords are used to define an abstract class? A processing unit that coordinates networks and data communication is known as