Nams's blog

By Nams, history, 5 years ago,

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?

• +3

 » 5 years ago, # |   0 You can do it in O(N * K) where N = length of the string and K = maximum possible 'distance'.
•  » » 5 years ago, # ^ |   0 You can give a hint??
•  » » » 5 years ago, # ^ |   0 Think of the possible states that you can visit in <= K moves.
•  » » » 5 years ago, # ^ |   0 Think of the diagonal of the matrix.
•  » » 5 years ago, # ^ |   0 But max possible distance could be of the order of n. Ain't it?
•  » » » 5 years ago, # ^ |   0 It is. But O(N * |solution|) is the best possible answer for this problem.
•  » » 3 years ago, # ^ |   0 Hi AlexandruValeanu , vontman, Nams, here do you need other state? with space complexity O(n*n*k) ??
 » 5 years ago, # |   +8 Probably one of algorithms could pass (where n, m are lengths of the strings and w is the size of processor word). For example, see "A Fast and Practical Bit-Vetor Algorithm for the Longest Common Subsequence Problem".
•  » » 5 years ago, # ^ |   0 Thanks :)
 » 7 weeks ago, # |   0 can you share the problem link?