72. Edit Distance

https://leetcode.com/problems/edit-distance/

• CTCI 1.5 One Away

Python

Bottom-up DP

word1\word2	""	a	p	p	l	e
""	0	1	2	3	4	5
r	1	1	2	3	4	5
a	2	1	2	3	4	5
d	3	2	2	3	4	5

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        dp = [[0]*(n+1) for _ in range(m+1)]

        for row in range(1, m+1):
            dp[row][0] = row
        for col in range(1, n+1):
            dp[0][col] = col


        for row in range(1, m+1):
            for col in range(1, n+1):
                if word1[row-1] == word2[col-1]:
                    dp[row][col] = dp[row-1][col-1]
                else:
                    dp[row][col] = min(
                        dp[row-1][col]+1,
                        dp[row][col-1]+1,
                        dp[row-1][col-1]+1
                    )

        return dp[m][n]

Javascript

var minDistance = function(word1, word2) {
    const dp = [...new Array(word1.length + 1)].map(() => new Array(word2.length + 1).fill(0))
    for (let i = 0; i <= word1.length; i++) {
        for (let j = 0; j <= word2.length; j++) {
            if (i === 0) dp[i][j] = j;
            else if (j === 0) dp[i][j] = i;
            else {
                if (word1[i - 1] === word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                        dp[i - 1][j] + 1,
                        dp[i - 1][j - 1] + 1,
                        dp[i][j - 1] + 1,
                    );
                }
            }
        }
    }

    return dp[word1.length][word2.length]
};

/**
 *   " h o r s e
 * " 0 1 2 3 4 5
 * r 1 1 2 2 3 4
 * o 2 2 1 2 3 4
 * s 3 3 2 2 2 3
 */

Rust

impl Solution {
    pub fn min_distance(word1: String, word2: String) -> i32 {
        let m = word1.len();
        let n = word2.len();
        let word1_bytes = word1.as_bytes();
        let word2_bytes = word2.as_bytes();

        let mut dp = vec![vec![0; n + 1]; m + 1];

        for row in 0..m {
            dp[row][0] = row;
        }
        for col in 0..n {
            dp[0][col] = col;
        }

        for row in 1..m+1 {
            for col in 1..n+1 {
                if word1_bytes[row-1] == word2_bytes[col-1] {
                    dp[row][col] = dp[row-1][col-1];
                    continue;
                }

                dp[row][col] = *vec![
                    1+dp[row-1][col],
                    1+dp[row][col-1],
                    1+dp[row-1][col-1]
                ].iter().min().unwrap();
            }
        }

        dp[m][n] as i32
    }
}