首页 > 动态规划 > 线性DP > LeetCode-Edit Distance[动态规划]
2014
11-19

LeetCode-Edit Distance[动态规划]

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

标签: Dynamic Programming String
分析

设状态为{f[i][j]},表示{A[0,i]}和{B[0,j]}之间的最小编辑距离。设{A[0,i]}的形式是{str1c},{B[0,j]}的形式是{str2d},
\begin{enumerate}
\item 如果{c==d},则{f[i][j]=f[i-1][j-1]};
\item 如果{c!=d},
\begin{enumerate}
\item 如果将c替换成d,则{f[i][j]=f[i-1][j-1]+1};
\item 如果在c后面添加一个d,则{f[i][j]=f[i][j-1]+1};
\item 如果将c删除,则{f[i][j]=f[i-1][j]+1};
\end{enumerate}
\end{enumerate}

代码1

// LeetCode, Edit Distance
// 二维动规,时间复杂度O(n*m),空间复杂度O(n*m)
class Solution {
public:
    int minDistance(const string &word1, const string &word2) {
        const size_t n = word1.size();
        const size_t m = word2.size();
        // 长度为n的字符串,有n+1个隔板
        int f[n + 1][m + 1];
        for (size_t i = 0; i <= n; i++)
            f[i][0] = i;
        for (size_t j = 0; j <= m; j++)
            f[0][j] = j;

        for (size_t i = 1; i <= n; i++) {
            for (size_t j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1])
                    f[i][j] = f[i - 1][j - 1];
                else {
                    int mn = min(f[i - 1][j], f[i][j - 1]);
                    f[i][j] = 1 + min(f[i - 1][j - 1], mn);
                }
            }
        }
        return f[n][m];
    }
};

代码2

// LeetCode, Edit Distance
// 二维动规+滚动数组
// 时间复杂度O(n*m),空间复杂度O(n)
class Solution {
public:
    int minDistance(const string &word1, const string &word2) {
        if (word1.length() < word2.length())
            return minDistance(word2, word1);

        int f[word2.length() + 1];
        int upper_left = 0; // 额外用一个变量记录f[i-1][j-1]

        for (size_t i = 0; i <= word2.size(); ++i)
            f[i] = i;

        for (size_t i = 1; i <= word1.size(); ++i) {
            upper_left = f[0];
            f[0] = i;

            for (size_t j = 1; j <= word2.size(); ++j) {
                int upper = f[j];

                if (word1[i - 1] == word2[j - 1])
                    f[j] = upper_left;
                else
                    f[j] = 1 + min(upper_left, min(f[j], f[j - 1]));

                upper_left = upper;
            }
        }

        return f[word2.length()];
    }
};

  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。