Edit Distance Problem in less than O(n^2) time

Revision en1, by Nams, 2016-10-24 15:01:06

I recently encountered a problem in a contest.It was very similar to edit distance.Only difference was that we are also given cost of each of the operation insert,delete and replace .We have to find minimum cost to convert string1 to string2. This problem is fairly standard and can be solved using dynamic programming in O(n^2) time. The problem statement for Edit Distance can be found here: Problem

But the constraints given in the contest were n<=100000 so larger test cases won't pass in O(n^2). So is there any way to bring the time complexity of the solution?

Tags edit distance, time complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Nams 2016-10-24 15:01:06 657 Initial revision (published)