Why it works
- Look at the last letters of the two prefixes. If they are equal, keeping them costs nothing, so the cell copies the diagonal.
- If they differ, the last edit is one of three: replace a’s letter with b’s (diagonal), delete a’s letter (above) or insert b’s letter (left). The cell is one more than the cheapest of them.
- The edges are exact: an empty prefix needs as many edits as the other prefix has letters. Every other cell is built from cells already filled, so the bottom-right cell is the true minimum.
Complexity
Time O(n × m) for words of lengths n and m: one cell per pair of prefixes, each from three neighbours. Memory O(n × m) for the table; the row above and the current row are enough, O(m).
nextNow solve it yourself, no hints.
Solve on LeetCode ↗