1.
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
A
O(1)
B
O(n+m)
C
O(mn)
D
O(nlogm)
Loading practice questions
7 practice sets · Page 1 of 1
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
What is the time complexity of the Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
Which of the following lines should be inserted to complete the above code?
arr[i][j] = min
(min = arr[i-1][j-1] - 1);
min = arr[i-1][j-1].
(min = arr[i-1][j-1] + 1);
For which of the following pairs of strings is the edit distance maximum?
sunday & monday
monday & tuesday
tuesday & wednesday
wednesday & thursday
What is the edit distance between the strings "abcd" and "acbd" when the allowed operations are insertion, deletion and substitution?
1
2
3
4
Wagner-Fischer algorithm is used to find ____________
Longest common subsequence
Longest increasing subsequence
Edit distance between two strings
Longest decreasing subsequence
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive