本文概述

• C++
• Java
• python
• C#
• PHP
• C++
• Java
• python
• C#
• PHP

给定两个字符串str1和str2及其以下的操作，可以在str1上执行。找出将' str1 '转换为' str2 '所需的最小编辑次数(操作)。

1. 插入insert
2. 删除remove
3. 替换replace

以上所有操作成本均相等。
例子：

Input:str1 = "geek", str2 = "gesek" Output:1 We can convert str1 into str2 by inserting a 's'.Input:str1 = "cat", str2 = "cut" Output:1 We can convert str1 into str2 by replacing 'a' with 'u'.Input:str1 = "sunday", str2 = "saturday" Output:3 Last three and first characters are same.We basically need to convert "un" to "atur".This can be done using below three operations. Replace 'n' with 'r', insert t, insert a

在这种情况下, 有哪些子问题？
这个想法是从两个字符串的左侧或右侧逐一处理所有字符。
让我们从右上角遍历, 遍历每对字符有两种可能性。

m: Length of str1 (first string) n: Length of str2 (second string)

1. 如果两个字符串的最后一个字符相同, 则无事可做。忽略最后一个字符并获得剩余字符串的计数。因此我们重复长度为m-1和n-1。
2. 否则(如果最后一个字符不同), 我们考虑对" str1"的所有操作, 考虑对第一个字符串的最后一个字符的所有三个操作, 递归计算这三个操作的最低成本, 并取三个值中的最小值。
   1. 插入：重复出现m和n-1
   2. 删除：重复执行m-1和n
   3. 替换：重复执行m-1和n-1

下面是上述Naive递归解决方案的C++实现。
C++

// A Naive recursive C++ program to find minimum number // operations to convert str1 to str2 #include < bits/stdc++.h> using namespace std; // Utility function to find minimum of three numbers int min( int x, int y, int z) { return min(min(x, y), z); }int editDist(string str1, string str2, int m, int n) { // If first string is empty, the only option is to // insert all characters of second string into first if (m == 0) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0) return m; // If last characters of two strings are same, nothing // much to do. Ignore last characters and get count for // remaining strings. if (str1[m - 1] == str2[n - 1]) return editDist(str1, str2, m - 1, n - 1); // If last characters are not same, consider all three // operations on last character of first string, recursively // compute minimum cost for all three operations and take // minimum of three values. return 1 + min(editDist(str1, str2, m, n - 1), // Insert editDist(str1, str2, m - 1, n), // Remove editDist(str1, str2, m - 1, n - 1) // Replace ); }// Driver program int main() { // your code goes here string str1 = "sunday" ; string str2 = "saturday" ; cout < < editDist(str1, str2, str1.length(), str2.length()); return 0; }

Java

// A Naive recursive Java program to find minimum number // operations to convert str1 to str2 class EDIST { static int min( int x, int y, int z) { if (x < = y & & x < = z) return x; if (y < = x & & y < = z) return y; else return z; }static int editDist(String str1, String str2, int m, int n) { // If first string is empty, the only option is to // insert all characters of second string into first if (m == 0 ) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0 ) return m; // If last characters of two strings are same, nothing // much to do. Ignore last characters and get count for // remaining strings. if (str1.charAt(m - 1 ) == str2.charAt(n - 1 )) return editDist(str1, str2, m - 1 , n - 1 ); // If last characters are not same, consider all three // operations on last character of first string, recursively // compute minimum cost for all three operations and take // minimum of three values. return 1 + min(editDist(str1, str2, m, n - 1 ), // Insert editDist(str1, str2, m - 1 , n), // Remove editDist(str1, str2, m - 1 , n - 1 ) // Replace ); }public static void main(String args[]) { String str1 = "sunday" ; String str2 = "saturday" ; System.out.println(editDist(str1, str2, str1.length(), str2.length())); } } /*This code is contributed by Rajat Mishra*/

python

# A Naive recursive Python program to fin minimum number # operations to convert str1 to str2 def editDistance(str1, str2, m, n):# If first string is empty, the only option is to # insert all characters of second string into first if m = = 0 : return n# If second string is empty, the only option is to # remove all characters of first string if n = = 0 : return m# If last characters of two strings are same, nothing # much to do. Ignore last characters and get count for # remaining strings. if str1[m - 1 ] = = str2[n - 1 ]: return editDistance(str1, str2, m - 1 , n - 1 )# If last characters are not same, consider all three # operations on last character of first string, recursively # compute minimum cost for all three operations and take # minimum of three values. return 1 + min (editDistance(str1, str2, m, n - 1 ), # Insert editDistance(str1, str2, m - 1 , n), # Remove editDistance(str1, str2, m - 1 , n - 1 )# Replace )# Driver program to test the above function str1 = "sunday" str2 = "saturday" print editDistance(str1, str2, len (str1), len (str2))# This code is contributed by Bhavya Jain

C#

// A Naive recursive C# program to // find minimum numberoperations // to convert str1 to str2 using System; class GFG { static int min( int x, int y, int z) { if (x < = y & & x < = z) return x; if (y < = x & & y < = z) return y; else return z; }static int editDist(String str1, String str2, int m, int n) { // If first string is empty, the only option is to // insert all characters of second string into first if (m == 0) return n; // If second string is empty, the only option is to // remove all characters of first string if (n == 0) return m; // If last characters of two strings are same, nothing // much to do. Ignore last characters and get count for // remaining strings. if (str1[m - 1] == str2[n - 1]) return editDist(str1, str2, m - 1, n - 1); // If last characters are not same, consider all three // operations on last character of first string, recursively // compute minimum cost for all three operations and take // minimum of three values. return 1 + min(editDist(str1, str2, m, n - 1), // Insert editDist(str1, str2, m - 1, n), // Remove editDist(str1, str2, m - 1, n - 1) // Replace ); }// Driver code public static void Main() { String str1 = "sunday" ; String str2 = "saturday" ; Console.WriteLine(editDist(str1, str2, str1.Length, str2.Length)); } }// This Code is Contributed by Sam007

PHP

< ?php // A Naive recursive Python program // to find minimum number operations // to convert str1 to str2 function editDistance( $str1 , $str2 , $m , $n ) { // If first string is empty, // the only option is to insert. // all characters of second // string into first if ( $m == 0) return $n ; // If second string is empty, // the only option is to // remove all characters of // first string if ( $n == 0) return $m ; // If last characters of two // strings are same, nothing // much to do. Ignore last // characters and get count // for remaining strings. if ( $str1 [ $m - 1] == $str2 [ $n - 1]) { return editDistance( $str1 , $str2 , $m - 1, $n - 1); }// If last characters are not same, // consider all three operations on // last character of first string, // recursively compute minimum cost // for all three operations and take // minimum of three values. return 1 + min(editDistance( $str1 , $str2 , $m , $n - 1), // Insert editDistance( $str1 , $str2 , $m - 1, $n ), // Remove editDistance( $str1 , $str2 , $m - 1, $n - 1)); // Replace } // Driver Code $str1 = "sunday" ; $str2 = "saturday" ; echo editDistance( $str1 , $str2 , strlen ( $str1 ), strlen ( $str2 )); // This code is contributed // by Shivi_Aggarwal ?>

输出如下：

3

上述解决方案的时间复杂度是指数的。在最坏的情况下, 我们可能最终会做O(3^m)操作。当两个字符串的字符都不匹配时, 会发生最坏的情况。下面是最坏情况的递归调用图。

文章图片
【计算从一个字符串转为另一个字符串的最小编辑次数| DP-5】我们可以看到, 许多子问题被一次又一次地解决了, 例如, eD(2, 2)被调用了三次。由于再次调用了相同的问题, 因此此问题具有"重叠子问题"属性。因此, "编辑距离"问题具有两个属性(请参见这个和这个)的动态编程问题。像其他典型的动态编程(DP)问题一样, 可以通过构造一个存储子问题结果的临时数组来避免相同子问题的重新计算。
C++

// A Dynamic Programming based C++ program to find minimum // number operations to convert str1 to str2 #include < bits/stdc++.h> using namespace std; // Utility function to find the minimum of three numbers int min( int x, int y, int z) { return min(min(x, y), z); }int editDistDP(string str1, string str2, int m, int n) { // Create a table to store results of subproblems int dp[m + 1][n + 1]; // Fill d[][] in bottom up manner for ( int i = 0; i < = m; i++) { for ( int j = 0; j < = n; j++) { // If first string is empty, only option is to // insert all characters of second string if (i == 0) dp[i][j] = j; // Min. operations = j// If second string is empty, only option is to // remove all characters of second string else if (j == 0) dp[i][j] = i; // Min. operations = i// If last characters are same, ignore last char // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1]; // If the last character is different, consider all // possibilities and find the minimum else dp[i][j] = 1 + min(dp[i][j - 1], // Insert dp[i - 1][j], // Remove dp[i - 1][j - 1]); // Replace } }return dp[m][n]; }// Driver program int main() { // your code goes here string str1 = "sunday" ; string str2 = "saturday" ; cout < < editDistDP(str1, str2, str1.length(), str2.length()); return 0; }

Java

// A Dynamic Programming based Java program to find minimum // number operations to convert str1 to str2 class EDIST { static int min( int x, int y, int z) { if (x < = y & & x < = z) return x; if (y < = x & & y < = z) return y; else return z; }static int editDistDP(String str1, String str2, int m, int n) { // Create a table to store results of subproblems int dp[][] = new int [m + 1 ][n + 1 ]; // Fill d[][] in bottom up manner for ( int i = 0 ; i < = m; i++) { for ( int j = 0 ; j < = n; j++) { // If first string is empty, only option is to // insert all characters of second string if (i == 0 ) dp[i][j] = j; // Min. operations = j// If second string is empty, only option is to // remove all characters of second string else if (j == 0 ) dp[i][j] = i; // Min. operations = i// If last characters are same, ignore last char // and recur for remaining string else if (str1.charAt(i - 1 ) == str2.charAt(j - 1 )) dp[i][j] = dp[i - 1 ][j - 1 ]; // If the last character is different, consider all // possibilities and find the minimum else dp[i][j] = 1 + min(dp[i][j - 1 ], // Insert dp[i - 1 ][j], // Remove dp[i - 1 ][j - 1 ]); // Replace } }return dp[m][n]; }public static void main(String args[]) { String str1 = "sunday" ; String str2 = "saturday" ; System.out.println(editDistDP(str1, str2, str1.length(), str2.length())); } } /*This code is contributed by Rajat Mishra*/

python

# A Dynamic Programming based Python program for edit # distance problem def editDistDP(str1, str2, m, n): # Create a table to store results of subproblems dp = [[ 0 for x in range (n + 1 )] for x in range (m + 1 )]# Fill d[][] in bottom up manner for i in range (m + 1 ): for j in range (n + 1 ):# If first string is empty, only option is to # insert all characters of second string if i = = 0 : dp[i][j] = j# Min. operations = j# If second string is empty, only option is to # remove all characters of second string elif j = = 0 : dp[i][j] = i# Min. operations = i# If last characters are same, ignore last char # and recur for remaining string elif str1[i - 1 ] = = str2[j - 1 ]: dp[i][j] = dp[i - 1 ][j - 1 ]# If last character are different, consider all # possibilities and find minimum else : dp[i][j] = 1 + min (dp[i][j - 1 ], # Insert dp[i - 1 ][j], # Remove dp[i - 1 ][j - 1 ])# Replacereturn dp[m][n]# Driver program str1 = "sunday" str2 = "saturday"print (editDistDP(str1, str2, len (str1), len (str2))) # This code is contributed by Bhavya Jain

C#

// A Dynamic Programming based // C# program to find minimum // number operations to // convert str1 to str2 using System; class GFG { static int min( int x, int y, int z) { if (x < = y & & x < = z) return x; if (y < = x & & y < = z) return y; else return z; }static int editDistDP(String str1, String str2, int m, int n) { // Create a table to store // results of subproblems int [, ] dp = new int [m + 1, n + 1]; // Fill d[][] in bottom up manner for ( int i = 0; i < = m; i++) { for ( int j = 0; j < = n; j++) { // If first string is empty, only option is to // insert all characters of second string if (i == 0)// Min. operations = j dp[i, j] = j; // If second string is empty, only option is to // remove all characters of second string else if (j == 0)// Min. operations = i dp[i, j] = i; // If last characters are same, ignore last char // and recur for remaining string else if (str1[i - 1] == str2[j - 1]) dp[i, j] = dp[i - 1, j - 1]; // If the last character is different, consider all // possibilities and find the minimum else dp[i, j] = 1 + min(dp[i, j - 1], // Insert dp[i - 1, j], // Remove dp[i - 1, j - 1]); // Replace } }return dp[m, n]; }// Driver code public static void Main() { String str1 = "sunday" ; String str2 = "saturday" ; Console.Write(editDistDP(str1, str2, str1.Length, str2.Length)); } } // This Code is Contributed by Sam007

PHP

< ?php // A Dynamic Programming based // Python program for edit // distance problem function editDistDP( $str1 , $str2 , $m , $n ) { // Fill d[][] in bottom up manner for ( $i = 0; $i < = $m ; $i ++) { for ( $j = 0; $j < = $n ; $j ++) { // If first string is empty, // only option is to insert // all characters of second string if ( $i == 0) $dp [ $i ][ $j ] = $j ; // Min. operations = j // If second string is empty, // only option is to remove // all characters of second string else if ( $j == 0) $dp [ $i ][ $j ] = $i ; // Min. operations = i // If last characters are same, // ignore last char and recur // for remaining string else if ( $str1 [ $i - 1] == $str2 [ $j - 1]) $dp [ $i ][ $j ] = $dp [ $i - 1][ $j - 1]; // If last character are different, // consider all possibilities and // find minimum else { $dp [ $i ][ $j ] = 1 + min( $dp [ $i ][ $j - 1], // Insert $dp [ $i - 1][ $j ], // Remove $dp [ $i - 1][ $j - 1]); // Replace } } } return $dp [ $m ][ $n ] ; }// Driver Code $str1 = "sunday" ; $str2 = "saturday" ; echo editDistDP( $str1 , $str2 , strlen ( $str1 ), strlen ( $str2 )); // This code is contributed // by Shivi_Aggarwal ?>

输出如下：

3

时间复杂度：O(m x n)
辅助空间：O(m x n)
复杂空间解决方案：在上述方法中, 我们需要O(m x n)空间。如果字符串的长度大于2000, 这将不合适, 因为它只能创建2000 x 2000的2D数组。要填充DP数组中的一行, 我们只需要在上一行中添加一行。例如, 如果要在DP数组中填充i = 10行, 则仅需要第9行的值。因此, 我们只需创建一个长度为2 x str1的DP数组。这种方法降低了空间复杂度。这是上述问题的C++实现。

// A Space efficient Dynamic Programming // based C++ program to find minimum // number operations to convert str1 to str2 #include < bits/stdc++.h> using namespace std; void EditDistDP(string str1, string str2) { int len1 = str1.length(); int len2 = str2.length(); // Create a DP array to memoize result // of previous computations int DP[2][len1 + 1]; // To fill the DP array with 0 memset (DP, 0, sizeof DP); // Base condition when second string // is empty then we remove all characters for ( int i = 0; i < = len1; i++) DP[0][i] = i; // Start filling the DP // This loop run for every // character in second string for ( int i = 1; i < = len2; i++) { // This loop compares the char from // second string with first string // characters for ( int j = 0; j < = len1; j++) { // if first string is empty then // we have to perform add character // operation to get second string if (j == 0) DP[i % 2][j] = i; // if character from both string // is same then we do not perform any // operation . here i % 2 is for bound // the row number. else if (str1[j - 1] == str2[i - 1]) { DP[i % 2][j] = DP[(i - 1) % 2][j - 1]; }// if character from both string is // not same then we take the minimum // from three specified operation else { DP[i % 2][j] = 1 + min(DP[(i - 1) % 2][j], min(DP[i % 2][j - 1], DP[(i - 1) % 2][j - 1])); } } }// after complete fill the DP array // if the len2 is even then we end // up in the 0th row else we end up // in the 1th row so we take len2 % 2 // to get row cout < < DP[len2 % 2][len1] < < endl; }// Driver program int main() { string str1 = "food" ; string str2 = "money" ; EditDistDP(str1, str2); return 0; }

输出如下：

4

时间复杂度：O(m x n)
辅助空间：O(m)
应用领域：编辑距离算法有很多实际应用, 请参考Lucene示例API。另一个示例, 显示词典中与给定单词拼写错误的单词接近的所有单词。
感谢Vivek Kumar建议更新。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

推荐阅读

• 

  601939股票走势行情 601939股票行情
• 

  苏贞昌自比袁崇焕，台媒：映照绿营争权砍得刀刀入骨
• 

  肝癌|这件事做1次，肝要“加7天班”解毒！再不注意，肝癌迟早找上门
• 

  荣耀小口哨怎么连接手机（荣耀小口哨怎么连接两台手机）
• 

  打造一张梦幻的紫色高光壁纸
• 

  三伏天羊肉怎么做才能去湿
• 

  十条清单，告诉你班主任该怎么做
• 

  台商投资区角美镇属于哪个区 角美是哪里
• 

  巨蟹座堵车的时候都在干什么 巨蟹座赌气的表现
• 

  国际学生证有什么用
• 

  九江人为什么叫九剥皮
• 

  胖子无忧 超有效的黑木耳减肥食谱
• 

  axure密码显示隐藏 axure如何将密码不可见，axure忘记密码
• 

  晚豆角什么时候种，东北地区晚豆角什么时候种
• 

  玉米淀粉可以做红糖糍粑吗
• 

  博世热水器老是显示e1是什么故障,出现这故障是什么原因
• 

  toyotires什么车 touareg什么车
• 

  python循环使用函数的简单介绍
• 

  如何简单消毒 消毒好方法
• 

  棘螈堪比大熊猫/仅剩1590只(世界上最珍稀的两栖动物）

• 分割字符串的方法，使每个分区以不同的字符开始
• Python编程（计算三个数最大值的3中方法）
• 巧妙处理电脑键盘右边的数字键失灵问题
• 注重笔记本保养 经常见故障区分及处理
• 你所不熟悉的显卡各种后缀字母的意义
• 高手详细说明液晶显示器的维护常识
• CPU选购秘籍 简单一招辨别原装与封盒
• 3步骤简单处理开机显示NTLDR is mis的问题
• 菜鸟购买电脑必读 小心这些误区