Trim and Extend a Word

Medium

You have a string word and need to turn it into the string goal. In one operation you may do one of four things: add a letter to the front, add a letter to the back, delete the first letter or delete the last letter. Letters in the middle cannot be changed. Return the smallest number of operations that makes word equal to goal.

Example 1

word="planet", goal="lane" → 2

Cut p off the front and t off the back, leaving lane. Two operations.

Example 2

word="stone", goal="tonic" → 4

The shared piece is ton. Drop s from the front and e from the back, then append i and c: 4 operations.

Example 3

word="abc", goal="xyz" → 6

No letters in common: remove all three and add three new ones, 6 operations.

Constraints

1 ≤ len(word), len(goal) ≤ 1000
Both strings consist of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Binary Search Dynamic Programming Sliding Window Hash Function

Similar problems

Longest Shared Run Medium Longest Piece Seen Twice Medium Target From Word Beginnings Medium Longest Repeated Fragment Hard Phrase From Word Beginnings, Long Edition Hard

Input

word="planet", goal="lane"

Expected

Run checks the first 3 tests in your browser. Submit checks all 145 tests on the server, hidden ones included.