Edit Distance(Dynamic Programming)

Edit Distance(Dynamic Programming)

Description

A problem on leetcode.

Definition

  • Given two strings $word1$ and $word2$
  • Do some operations to convert word1 to word2
  • Insert\delete\repalce 1 character is counted as one step
  • Find the minimum steps to complete this process
    For example:
    It will take 2 steps to convert $abc$ to $a$ by delete 2 times.

Analyse

  • We define $D(i,j)$ : the minimun steps needed when we convert $word1[i]$ to $word2[j]$
  • If we know the value of $D(i-1,j-1), D(i,j-1),D(i-1,j)$, then we can deduce the $D(i,j)$(it is easy to acquire)
    $$
    D(i,j) = min\begin{cases}
    D(i-1,j) + 1 \
    D(i,j-1)\ +\ 1\
    D(i-1,j-1) + \begin{cases}
    0 &if\ word1[i]\ ==\ word2[j]\
    1 &if\ word1[i]\ !=\ word2[j]
    \end{cases}
    \end{cases}
    $$
  • We assume replace operation as one step, however, sometimes it maybe ruled as two steps. In that way, the branch of $D(i-1,j-1)$will be :

$$D(i-1,j-1) + \begin{cases}
0 &if\ word1[i]\ ==\ word2[j]\
2 &if\ word1[i]\ !=\ word2[j]
\end{cases}$$

  • We got an example:
    • The table show the process to get $D(9,9)$ where the $word1$ is INTENTION and the $word2$ is EXECUTION
    • The elements on the left edge or the bottom of the table can be acquired easily.
    • We can use recursion to obtain the full table.

Implement

  • From the Analyse , we can use a table to obtain the result. And the space costed is $O(mn)$ .
  • In fact, by saving the last line, we can achieve the next line. The space costed will be decreased to $O(n)$ or $O(m)$.
  • C++ code:
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m(word1.size()),n(word2.size());
        vector<int> curCol(m+1,0);
        iota(curCol.begin(),curCol.end(),0);
        for(int i(1); i <= n; ++i)
        {
            int preCol = curCol[0];
            curCol[0] = i;
            for(int j(1); j <= m; ++j)
            {
                int buf = curCol[j];
                int add = (word1[j - 1]==word2[i - 1]) ? 0 : 1 ;
                curCol[j] = min( preCol + add, min( curCol[j] + 1, curCol[j - 1] + 1));
                preCol = buf;
            }
        }
        return curCol[m];

    }
};

Reference

Comments are closed.