How should I practice Edit Distance?

Start by reading the full statement, solve the visible examples, then compare the pattern against related DP World phone screen problems in FastPrep.

Is Edit Distance associated with DP World?

FastPrep tags this as a DP World phone screen coding practice problem when the problem catalog has that company and stage context.

Edit Distance

DP World● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given two strings, word1 and word2. Return the minimum number of operations needed to turn word1 into word2.

Each operation changes the word by one character in one of these ways:

Insert a character.
Delete a character.
Replace a character with a different character.

Follow-up

After you find the minimum, how would you list the operation used at each step of one shortest sequence? Your function only returns the number. The editorial shows how to recover the steps.

Function

minDistance(word1: String, word2: String) → int

Examples

Example 1

word1 = "horse"word2 = "ros"return = 3

Three operations are enough:

Replace 'h' with 'r': horse becomes rorse.
Delete the second 'r': rorse becomes rose.
Delete 'e': rose becomes ros.

Two operations are not enough. Going from five letters to three needs at least two deletions, so both operations would be deletions. Deleting letters keeps the order of the others, and horse has no 'o' after its 'r', so deletions alone cannot give ros.

Example 2

word1 = "intention"word2 = "execution"return = 5

Five operations are enough:

Delete 't': intention becomes inention.
Replace 'i' with 'e': inention becomes enention.
Replace 'n' with 'x': enention becomes exention.
Replace 'n' with 'c': exention becomes exection.
Insert 'u': exection becomes execution.

Example 3

word1 = ""word2 = "abc"return = 3

word1 is empty, so every letter of abc has to be inserted. That takes three operations.

Constraints

0 <= word1.length, word2.length <= 500
word1 and word2 contain only lowercase English letters.