Leetcode 72 Solution

This article provides solution to leetcode question 72 (edit-distance)
Categories:
Tags:
Access this page by simply typing in "lcs 72" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();

        if (m == 0)
            return n;
        if (n == 0)
            return m;

        int dp[m][n];

        dp[0][0] = word1[0] != word2[0];

        for (int j = 1; j < n; j++)
            dp[0][j] = min(dp[0][j - 1] + 1, (int)(word1[0] != word2[j]) + j);

        for (int i = 1; i < m; i++)
            dp[i][0] = min(dp[i - 1][0] + 1, (int)(word1[i] != word2[0]) + i);

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (int)(word1[i] != word2[j]));
            }
        }

        return dp[m - 1][n - 1];
    }
};