String Edit Distance

medium

Dynamic ProgrammingStringDp 2d

Asked atGoogleAmazonMicrosoftMetaApple

Problem Description

Given two strings `source` and `target`, return the minimum number of operations needed to transform `source` into `target`.

The allowed operations are:
- **Insert** a character at any position.
- **Remove** a character from any position.
- **Replace** a character with a different character.

Each operation counts as a single step.

**Example 1:**
```
Input: source = "kitten", target = "sitting"
Output: 3
Explanation:
kitten → sitten (replace 'k' with 's')
sitten → sittin (replace 'e' with 'i')
sittin → sitting (insert 'g')
```

**Example 2:**
```
Input: source = "flaw", target = "lawn"
Output: 2
Explanation: Remove 'f' and append 'n'.
```

Constraints

0 <= source.length <= 500
0 <= target.length <= 500
Both strings consist of lowercase English letters only.

Follow-up

Can you reduce the space complexity to O(min(m, n)) using only two rolling arrays?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.