Trim Two Words to Match
Problem
In a word game you may delete one character at a time from either of two words, first or second. Each deletion is one move.
Return the minimum number of moves needed to make the two words identical (both may end up empty).
Example 1
- Input:
- first = "route", second = "outer"
- Output:
- 2
Delete "r" from "route" and "r" from "outer": both become "oute".
Example 2
- Input:
- first = "seat", second = "set"
- Output:
- 1
Delete "a" from "seat".
Constraints
- 0 ≤ first.length, second.length ≤ 1000
- Both strings contain lowercase English letters only.
Hint
Show the first hint
Whatever survives in both words is a common subsequence.
Walkthrough
How to approach it
01Clarify before coding
- Only deletions? Yes, no insertions or replacements.
- Do deletions from either word cost the same? Yes, 1 each.
- May both words become empty? Yes, deleting everything is always valid.
02Brute force
Recursively compare the first characters: if equal, move both forward; otherwise try deleting from one word or the other.
Cost: O(2^(m + n)) without memoisation, because the same suffix pairs are solved over and over.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.