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}(NM)~, which will pass, but since you require an array ~dp~ of size ~\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}(NM)~