Delete Operation for Two Strings

Standard Bar Dynamic Programming · DP on Strings O(n*m) · O(min(n, m))

The Twin Ledger Reconciliation

An auditor holds two transaction ledgers that must end up character-for-character identical. The only legal correction is deleting one entry from either ledger at a time. Finance wants the smallest number of deletions that reconciles both books, so the reconciliation engine measures how much of the two ledgers already agrees.

Input: Two strings word1 and word2.

Output: Return how many single-character deletions (from either string) are needed to make the two strings equal.

Constraints

1 <= len(word1), len(word2) <= 500
strings consist of lowercase English letters

Examples

Example 1

Input: {"word1":"sea","word2":"eat"}
Output: 2
Delete 's' from "sea" and 't' from "eat" — both become "ea" in two steps.

Example 2

Input: {"word1":"leetcode","word2":"etco"}
Output: 4
The shared anchor "etco" survives; the four surrounding characters get deleted.

Solve this in your browser →

Also on LeetCode ↗