编辑距离

public class Solution {
    /**
    * 题目解析：
    * 1. 本题涉及动态规划 - Dynamic Programming
    * 之所以翻译成动态规划，是因为发明者是数学家，Programming不是CS中的编程，应该理解为规划或计划
    *    该解释参考自算法设计与分析基础》
    * 2. 给定两个单词word1和word2，需要将word1转换为word2
    *    转换的条件是只能执行：插入一个字符，删除一个字符，替换一个字符
    *    这三种操作，没执行一次，算一步，求word1转换为word2所需最小步数
    *
    * 解题思路：
    * 1. 动态规划解题思路为： 拆分为子问题 - 找出递归式
    * 2. 动态规划 需要用最优解来填充一张表 - 可能是一维表 or 二维表
    * 
    * 问题举例理解： “ab” 到 “abc” 的最小步数
    * 所有子问题：
    * 0. "" 到 "a"【及  到 "ab" 及 到 "abc"】的最优解
    * 1. "a" 到 "a" 【及  到 "ab" 及 到 "abc"】的最优解
    * 2. "ab" 到 "a" 【及  到 "ab" 及 到 "abc"】的最优解
    * 用这些最优解填充一张二维表 表的右下角为 整个问题的"ab" 到 "abc"的最优解
    * 二维表：#代表空字符串
    * 0 # a b c
    * # 0 1 2 3
    * a 1 0 1 2
    * b 2 1 0 1
    * 由表可知 由"ab" 到 "abc" 最优解：只需进行一步
    * 
    * 递推公式：
    * F(i,j) 代表word1的前i -1个字符组成的字符串到 word2的前j -1个字符组成的字符串的最优解
    * 例：F(2, 3) 代表word1的前1个字符组成的字符串到 word2的前2个字符组成的字符串的最优解
    * 若 i == j,则意为着不需额外操作，则F(i,j) 显然 等于 F(i - 1,j - 1)
    * 若 i != j,则肯定需要1步操作来转换
    * 以 "ab" 到 "abc"为例，该最优解为： min{"a" 到 "abc"的最优解, "ab" 到 "ab"的最优解，"a" 到 "ab" 的最优解 } + 1
    * 所以 该情况递推公式为：F(i,j) = min{F(i - 1, j), F(i, j - 1),F(i - 1, j - 1) } + 1
    *
    */
    public int minDistance(String word1, String word2) {
        // 获取字符串长度 以便建立二维表
        int len1 = word1.length();
        int len2 = word2.length();

        // 建立dp表
        int[][] dp = new int[len1 + 1][len2 + 1];

        // 初始化表

        // 第一行为 空字符串 到 对应字符串 所需 转换步数
        for (int i = 0; i <= len2; i++) {
            dp[0][i] = i;
        }
        // 第一列为 空字符串 到 对应字符串 所需 转换步数
        for (int i = 0; i <= len1; i++) {
            dp[i][0] = i;
        }

        // 比较 字符 填充dp表其余部分
        // 跳过第一行第一列：因为已经初始化填充了
        for (int i = 1; i <= len1; i++) { // word1
            for (int j = 1; j <= len2; j++) { // word2
                // i 索引对应值== j 索引对应值，F(i, j ) = F(i - 1, j - 1)
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 其他情况
                    // 取min{F(i - 1, j - 1) F(i - 1, j) F(i, j - 1) } + 1
                    int temp = Math.min(dp[i - 1][j] , dp[i][j - 1]);
                    dp[i][j] = Math.min(temp, dp[i - 1][j - 1]) + 1;
                }
            }
        }

        return dp[len1][len2];
    }
}

public class Solution {
    public int minDistance(String word1, String word2) {
        if(word1 == null && word2 == null)
        	return 0;
        if(word1 == null)
        	return word2.length();
        if(word2 == null)
        	return word1.length();
        
        // dp[i][j]代表由word1的前i个子串变为word2的前j个子串的花费
        // 其中i，j均可为0，代表空串:""
        int[][] dp = new int[word1.length() + 1][word2.length() + 2];
        dp[0][0] = 0;
        // 首先初始化两个子串中有一个为空串的情况
        for(int i = 1; i <= word1.length(); i++){
        	dp[i][0] = i;
        }
        for(int j = 1; j <= word2.length(); j++){
        	dp[0][j] = j;
        }
        
        for(int i = 1; i <= word1.length(); i++){
        	for(int j = 1; j <= word2.length(); j++){
        		// 如果这两个字符相等，那么交由上一种情况处理,如abc，dfc
        		// 这种情况与ab，df花费是一样的
        		// 不然就要在删除，插入，修改中取花费最小的那个
        		if(word1.charAt(i - 1) == word2.charAt(j - 1))
        			dp[i][j] = dp[i-1][j-1];
        		else
        			dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

public class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < dp[0].length; i ++ ) dp[0][i] = i;
        for (int i = 0; i < dp.length; i ++ ) dp[i][0] = i;
        for (int i = 1; i < dp.length; i ++ ) {
            for (int j = 1; j < dp[0].length; j ++ ) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length();
        int n = word2.length();
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++)
        	dp[i][0] = i;
        for(int j=1;j<=n;j++)
        	dp[0][j] = j;
        for(int i=1;i<=m;i++)
        	for(int j=1;j<=n;j++)
        	{
        		if(word1[i-1] == word2[j-1])
        			dp[i][j] = dp[i-1][j-1];
        		else
        			dp[i][j] = min(dp[i-1][j]+1, min(dp[i][j-1]+1, dp[i-1][j-1]+1));
			}
    	return dp[m][n];
	}
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        //return dfs(word1, word2, 0);
        // 非递归动态规划法：
        // word2 = [a, b, d], word1 = [a, b]
        // 则假设我们已经求出了word1的[0,0]位置的最小操作，那么当新增一个字符b时，有如下的计算匹配：
        // 第一轮：令i = 1, j = 0, 使word1[i]依次匹配word2的[0, 2]位置的字符
        //    [a, b, c]
        // [a, b]
        // 则此时的计算结果就为  dp[1][0] = 1(删除word1中的a字符) + 1(替换单词b)
        // 第二轮：令i = 1, j = 1, 使word1[i]依次匹配word2的[1, 2]位置的字符
        //   [a, b, c]
        //   [a, b]
        // 则此时的计算结果为dp[1][1] = dp[0][0] + 0(b字符已经相同无须变换)
        // 第三轮：令i = 1, j = 2，使word1[i]依次匹配word2的[2, 2]位置的字符
        //   [a, b, c]
        //      [a, b]
        // 刚此时的计算结果为dp[1][2] = dp[0][1] + 1(替换单词b)，
        // 但还需要跟上一轮的结果作比较，因为此时的结果有可能小于在上一轮匹配位置之后，直接插入第j个字符后的结果，
        // dp[1][2] = min(dp[1][2], dp[1][1] + 1)
        // 或是小于没有添加当前字符时的匹配结果
        // dp[1][2] = min(dp[1][2], dp[0][2] + 1)
        // 最终得到一张二维表：
        //   #  ""  a  b  c
        //   "" 0   1  2  3
        //   a  1   0  1  2
        //   b  2   2  0  1
        // 基本的流程就如上所示，但还需要确认一下初始条件和边界条件
        // 初始条件：
        //   y轴为word1，x轴为word2，由于在比较的过程中需要统计删除word1的前[0, i]字符的步数，因为在横纵坐标的
        //   初始位置添加空的字符串便于计算
        // 边界条件：
        //   word1.length() == 0 || word2.length() == 0
        //
        int w1 = word1.length(), w2 = word2.length();
        if (w1 == 0) return w2;
        if (w2 == 0) return w1;
        int dp[w1+1][w2+1];
        for (int i = 0; i <= w1; i++) dp[i][0] = i;
        for (int i = 0; i <= w2; i++) dp[0][i] = i;
        for (int i = 1; i <= w1; i++) {
            for (int j = 1; j <= w2; j++) {
                int cur_steps = dp[i-1][j-1] + (word1[i-1] != word2[j-1]); // 替换操作
                dp[i][j] = min(cur_steps, dp[i][j-1] + 1);                 // 插入操作
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);                  // 删除操作
            }
        }
        return dp[w1][w2];
    }

public class Solution {
    public int maxValue=1000000000;
    public int search (int [][]f,String word1, String word2,int x,int y){
        if(x > word1.length() || y >word2.length()){
            return maxValue;
        }
        if(x == word1.length()  && y == word2.length()){
            return 0;
        }
        if(f[x][y]>0){
            return  f[x][y];
        }
        if(x<word1.length()&& y<word2.length()&& word1.charAt(x) == word2.charAt(y)){
            return f[x][y] = search(f,word1,word2,x+1,y+1);
        }else {
            return f[x][y] = Math.min(search(f,word1,word2,x,y+1),Math.min(search(f,word1,word2,x+1,y),search(f,word1,word2,x+1,y+1)))+1;
        }
    }
    public  int minDistance(String word1, String word2) {
        if(word1==null || word2 == null) return 0;
        if(word1.length() ==0 && word2.length()==0) return 0;
        if(word1.length() ==0 ) return word2.length();
        if(word2.length() ==0 ) return word1.length();
        int f[][] = new int [word1.length()+1][word2.length()+1];
        return search(f,word1,word2,0,0);
    }
}

public class Solution {
    public int minDistance(String word1, String word2) {
        int row = word1.length();
        int column = word2.length();
        int[][] distance = new int[row+1][column+1];
        for (int i = 0; i < column + 1; i++) distance[0][i] = i;
        for (int i = 0; i < row + 1; i++) distance[i][0] = i;
        for (int i = 1; i < row + 1; i++) {
            for (int j = 1; j < column + 1; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    distance[i][j] = distance[i-1][j-1];
                } else {
                    int temp = distance[i-1][j-1] < distance[i][j-1] ? distance[i-1][j-1] : distance[i][j-1];
                    int min = temp < distance[i-1][j] ? temp : distance[i-1][j];
                    distance[i][j] = min + 1;
                }
            }
        }
        return distance[row][column];
    }
}

对应三种字符操作方式：

edit[i-1][j]+1相当于给word2的最后插入了word1的最后的字符，插入操作使得edit+1，之后计算edit[i-1][j]；

edit[i][j-1]+1相当于将word2的最后字符删除，删除操作edit+1，之后计算edit[i][j-1];

edit[i-1][j-1]+flag相当于通过将word2的最后一个字符替换为word1的最后一个字符。flag标记替换的有效次数。

//动态规划ok
class Solution {
public:    
    int minDistance(string word1, string word2) 
    {
        int l1=word1.length();
        int l2=word2.length();
        if (l1 == 0 || l2 == 0)
            return max(l1, l2);
        vector<vector<int>> co(l1+1,vector(l2+1,INT_MAX));
        for(int i=0;i<=l1;i++)        
            co[i][0]=i;
        for(int j=0;j<=l2;j++)
            co[0][j]=j;
        for(int i=1;i<=l1;i++)
        {
            for(int j=1;j<=l2;j++)
            {
                co[i][j]=co[i-1][j-1]+1; //replace
                if(word1[i-1]==word2[j-1])
                    co[i][j]--;   //don't need replacement
                co[i][j]=min(co[i][j],co[i][j-1]+1);  //delete
                co[i][j]=min(co[i][j],co[i-1][j]+1);  //insert
            }
        }
        return co[l1][l2];
    }
};
//超时递归
class Solution {
public:
    int mini;
    void core(string w1,string w2,int idx1,int idx2,int l1,int l2,int cnt)
    {
        if(cnt>mini)
            return;
        if(idx1>=l1||idx2>=l2)
        {
            if(idx2<l2)
                cnt+=l2-idx2;
            else if(idx1<l1)
                cnt+=l1-idx1;
            mini=min(mini,cnt);
            return;
        }        
        if(w1[idx1]==w2[idx2])
            core(w1,w2,idx1+1,idx2+1,l1,l2,cnt);           
        else
            core(w1,w2,idx1+1,idx2+1,l1,l2,cnt+1);//replace
        core(w1,w2,idx1,idx2+1,l1,l2,cnt+1);//insert
        core(w1,w2,idx1+1,idx2,l1,l2,cnt+1);//delete
    }
    int minDistance(string word1, string word2) 
    {
        int l1=word1.length();
        int l2=word2.length();
        if(l1==0||l2==0)
            return max(l1,l2);
        mini=INT_MAX;
        core(word1,word2,0,0,l1,l2,0);
        return mini;
    }
};

public class Solution {
    public int minDistance(String word1, String word2) {
        char[] chs = word1.toCharArray() ; 
        char[] cht = word2.toCharArray() ; 
        int n = chs.length ; 
        int m = cht.length ;
        if(n == 0 || m == 0){
            return Math.abs(n-m) ; 
        }
        int[][] dp = new int[chs.length][cht.length] ; 
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                dp[i][j] = n+m ; 
            }
        }
        boolean flag = false ; 
        for(int i = 0;i < n;i++){
            if(chs[i] == cht[0]){
                flag = true ; 
            }
            dp[i][0] = flag ? i:i+1 ; 
        }
        flag = false ; 
        for(int j = 0;j < m;j++){
            if(chs[0] == cht[j]){
                flag = true ; 
            }
            dp[0][j] = flag ? j:j+1 ; 
        }
        for(int i = 1;i < n;i++){
            for(int j = 1;j < m;j++){
                int num = chs[i] == cht[j] ? 0 : 1 ; 
                dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j]) ; 
                dp[i][j] = Math.min(dp[i][j-1]+1,dp[i][j]) ; 
                dp[i][j] = Math.min(dp[i-1][j-1]+num,dp[i][j]) ; 
            }
        }
        return dp[n-1][m-1] ; 
    }
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1=word1.size(),len2=word2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1));
        for(int i=0;i<=len1;++i)
            dp[i][0]=i;
        for(int j=0;j<=len2;++j)
            dp[0][j]=j;
        for(int i=1;i<=len1;++i){
            for(int j=1;j<=len2;++j){
                dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1));
            }
        }
        return dp[len1][len2];
    }
};

public int minDistance(String word1, String word2) {
		if (word1 == null || word2 == null)
			return 0;
		int[][] res = new int[word1.length() + 1][word2.length() + 1];
		for (int i = 0; i <= word1.length(); i++) {
			res[i][0] = i;
		}
		for (int j = 0; j <= word2.length(); j++) {
			res[0][j] = j;
		}

		for (int i = 0; i < word1.length(); i++) {
			for (int j = 0; j < word2.length(); j++) {
				if (word1.charAt(i) == word2.charAt(j))
					res[i + 1][j + 1] = res[i][j];
				else {
					res[i + 1][j + 1] = 1 + min(res[i + 1][j], res[i][j + 1], res[i][j]);
				}
			}
		}

		return res[word1.length()][word2.length()];
	}

	private int min(int i, int j, int k) {
		int min = Math.min(i, j);
		min = Math.min(min, k);
		return min;
	}

int minDistance(string word1, string word2) {
    int l1 = word1.size(), l2 = word2.size();
    if(l1 == 0) return l2;
    if(l2 == 0) return l1;
    vector<vector<int>> dp(l1+1, vector<int>(l2+1, 0));
    
    for(int i = 0; i <= l1; ++i)
        dp[i][0] = i;
    for(int j = 0; j <= l2; ++j)
        dp[0][j] = j;
    
    for(int m = 1; m <= l1; ++m){
        for(int n = 1; n <= l2; ++n){
            if(word1[m-1] == word2[n-1])
                dp[m][n] = dp[m-1][n-1];
            else{
                int min1 = min(dp[m-1][n]+1, dp[m][n-1]+1);
                dp[m][n] = min(min1, dp[m-1][n-1]+1);
            }
        }
    }
    return dp[l1][l2];
}

class Solution {
public:
    
    // dp[i][j]代表由word1的前i个子串变为word2的前j个子串的花费
   int minDistance(string word1, string word2)
    {
      int m = word1.length(),n =  word2.length();
      vector<vector<int> > dp(m+1,vector<int>(n+1,0));
      for(int i=1;i<=m;i++)
         dp[i][0] = i; /// delete i chars of word1
      for(int j=1;j<=n;j++)
         dp[0][j] = j;  /// insert j chars of word2
       for(int i=1;i<=m;i++)
       {
           for(int j=1;j<=n;j++)
            {
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1)); /// delete,insert,replace
            }
       }
       return dp[m][n];
    }
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int> >dp(m+1,vector<int>(n+1));
        for(int i = 0;i <= m ;i++){
            for(int j = 0; j <= n ;j++){
                if(i ==0){
                    dp[i][j] = j;
                }
                else if(j ==0){
                    dp[i][j] = i;
                }
                else{
                    dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1)));
                }
            }
        }
        return dp[m][n];
    }
};

    int minDistance(string word1, string word2) {
        // write code here
        int m = word1.length();
        int n = word2.length();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        //设置边界
        for(int i=1;i<=m;++i)dp[i][0]=i;
        for(int i=1;i<=n;++i)dp[0][i]=i;
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=n;++j)
            {
                int n = 1;
                if(word1[i-1]==word2[j-1])
                    n = 0;
                dp[i][j] = min(dp[i-1][j-1]+n,min(dp[i-1][j],dp[i][j-1])+1);
            }
        }
        return dp[m][n];
    }
};