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?
You can do it in O(N * K) where N = length of the string and K = maximum possible 'distance'.
You can give a hint??
Think of the possible states that you can visit in <= K moves.
Think of the diagonal of the matrix.
But max possible distance could be of the order of n. Ain't it?
It is. But O(N * |solution|) is the best possible answer for this problem.
Hi AlexandruValeanu , vontman, Nams, here do you need other state? with space complexity O(n*n*k) ??
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".
Thanks :)
can you share the problem link?