Delete Operation for Two Strings
Medium · dynamic programming
You are given two words, s and t. In one step you may delete a single letter from either word, from any position.
Return the fewest steps needed to make the two words exactly equal.
Either word may be empty, and two empty words are equal. If the words are already equal, the answer is 0. In the worst case you can delete every letter from both words, so an answer always exists.
Examples
Example 1
Input: s = "sweet", t = "meet"
Output: 3
Delete "s" and "w" from the first word and "m" from the second. Both become "eet".
Example 2
Input: s = "abc", t = "abc"
Output: 0
The words are already equal.
Example 3
Input: s = "xyz", t = "pq"
Output: 5
No letter is shared, so every letter of both words has to go.
Constraints
- 0 <= len(s), len(t) <= 1000
- Both words contain only lowercase English letters.