Editorial for RGPC '17 P5 - Scrabble Nuts


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: chenj

This problem is simply minimum edit distance, but requires you to calculate the edit distance to all of the prefixes of a word. Given two strings A and B, the edit distance between them is the minimum number of operations (insertions/deletions/swaps) required to transform A into B.

Using dynamic programming, the time complexity of minimum edit distance is \mathcal{O}(N \times M), which will pass, but since you require an array dp of size \text{max}(N^2, M^2), you will run out of memory. To save memory, only store the previous row of states, because anything more is unnecessary. To calculate the final answer, loop through each state and add its value to your result.

Time complexity: \mathcal{O}(M \times N)


Comments

There are no comments at the moment.