Edit Distance
Post
Cancel

# LeetCode #72: Edit Distance (C/C++).

hard

source: https://leetcode.com/problems/edit-distance/
C/C++ Solution to LeetCode problem 72. Edit Distance.

## Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

## Examples

### Example 1:

Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)

### Example 2:

Input: word1 = “intention”, word2 = “execution”
Output: 5
Explanation:
intention -> inention (remove ‘t’)
inention -> enention (replace ‘i’ with ‘e’)
enention -> exention (replace ‘n’ with ‘x’)
exention -> exection (replace ‘n’ with ‘c’)
exection -> execution (insert ‘u’)

## Constraints

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

## Solution

For this problem, we will use Dynamic Programming.

• We need a map/vector to store the computed values.
• We actually don’t need to modify the words to find a solution.
• Using two pointers (one for each word), we will move them according to this:
• Move first pointer: it means we deleted the character.
• Move the second pointer: it means that we inserted that character in the first word, so we move to the next one.
• Move both characters: it means we replace the character (or it was the same a no need to do anything).
• When a pointer arrives to the end, we return the size of the other word minus the pointer of the current word.
• If we computed the solution before (found in the map/vector) then we return that value and no need to explore more.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { private: vector<vector<int>> dp; int solve(int i, int j, string &w1, string &w2){ if (i >= w1.size()) return w2.size() - j; if (j >= w2.size()) return w1.size() - i; if (dp[i][j] != -1) return dp[i][j]; if (w1[i] == w2[j]) dp[i][j] = solve(i+1, j+1, w1, w2); else { int min1 = solve(i+1, j, w1, w2); int min2 = solve(i, j+1, w1, w2); int min3 = solve(i+1, j+1, w1, w2); dp[i][j] = 1 + min(min(min1, min2), min3); } return dp[i][j]; } public: int minDistance(string word1, string word2) { dp = vector(word1.size(),vector<int>(word2.size(),-1)); return solve(0, 0, word1, word2); } };