Saturday, November 5, 2016

LeetCode OJ - Edit Distance

Problem:

Please find the problem here.

Analysis:

As a disclaimer, I have seen and implemented this problem in various context before. But by the time I implement this problem, the memory isn't fresh, but I vaguely remember it is a 2 dimensional dynamic programming.

Let's start with some notations:

Let strings be capital letter, and letter be lower case letter, for example, aX means a string starting with a.

Let m be the edit distance

The key recursive relationship is as follow

m("","") = 0
m(x, "") = m("", x) = |x|
m(aX, aY) = m(X, Y)
m(aX, bY) = min(m(aX, Y) + 1, m(X, bY) + 1, m(X, Y) + 1))

Case 1 is trivial.
Case 2 say if you wanted to edit a string to become an empty string, you must delete all characters.
Case 3 say if you have a matching character, the only rational thing to do is to move on without any editing at all.
Case 4 say if you have a mismatch, just try every possible thing.

Solution: 

With those formula, encode the two parameters as the length of the suffixes of the input string. The first two rule basically gives us the top row and the left most column. All the remaining rule only look at value either above or to the left, therefore we can build up the whole table and finally give the answer.

Code:

#include "stdafx.h"

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

#include "LEET_EDIT_DISTANCE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_EDIT_DISTANCE
{
    class Solution
    {
    public:
        int minDistance(string word1, string word2)
        {
            // m("","") = 0
            // m(x, "") = m("", x) = |x|
            // m(aX, aY) = m(X, Y)
            // m(aX, bY) = min(m(aX, Y) + 1, m(X, bY) + 1, m(X, Y) + 1))
            vector<vector<int>> m;
            m.resize(word1.length() + 1);
            for (int i = 0; i <= word1.length(); i++)
            {
                m[i].resize(word2.length() + 1);
            }

            for (int i = 0; i <= word1.length(); i++)
            {
                m[i][0] = i;
            }
            for (int i = 0; i <= word2.length(); i++)
            {
                m[0][i] = i;
            }

            for (int i = 0; i < word1.length(); i++)
            {
                for (int j = 0; j < word2.length(); j++)
                {
                    if (word1[i] == word2[j])
                    {
                        m[i + 1][j + 1] = m[i][j];
                    }
                    else
                    {
                        m[i + 1][j + 1] = min(min(m[i][j], m[i + 1][j]), m[i][j + 1]) + 1;
                    }
                }
            }
#ifdef LOG
            for (int i = 0; i <= word1.length(); i++)
            {
                for (int j = 0; j <= word2.length(); j++)
                {
                    cout << m[i][j] << " ";
                }
                cout << endl;
            }
#endif
            return m[word1.length()][word2.length()];
        }
    };
};

using namespace _LEET_EDIT_DISTANCE;

int LEET_EDIT_DISTANCE()
{
    Solution solution;
    cout << solution.minDistance("10086", "12580") << endl;
    return 0;
}

No comments :

Post a Comment