برنامه محاسبه فاصله ویرایش — به زبان ساده

1// A Naive recursive C++ program to find minimum number 
2// operations to convert str1 to str2 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6// Utility function to find minimum of three numbers 
7int min(int x, int y, int z) 
8{ 
9   return min(min(x, y), z); 
10} 
11  
12int editDist(string str1 , string str2 , int m ,int n) 
13{ 
14    // If first string is empty, the only option is to 
15    // insert all characters of second string into first 
16    if (m == 0) return n; 
17  
18    // If second string is empty, the only option is to 
19    // remove all characters of first string 
20    if (n == 0) return m; 
21  
22    // If last characters of two strings are same, nothing 
23    // much to do. Ignore last characters and get count for 
24    // remaining strings. 
25    if (str1[m-1] == str2[n-1]) 
26        return editDist(str1, str2, m-1, n-1); 
27  
28    // If last characters are not same, consider all three 
29    // operations on last character of first string, recursively 
30    // compute minimum cost for all three operations and take 
31    // minimum of three values. 
32    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert 
33                     editDist(str1,  str2, m-1, n),   // Remove 
34                     editDist(str1,  str2, m-1, n-1) // Replace 
35                   ); 
36} 
37  
38// Driver program 
39int main() 
40{ 
41    // your code goes here 
42    string str1 = "sunday"; 
43    string str2 = "saturday"; 
44  
45    cout << editDist( str1 , str2 , str1.length(), str2.length()); 
46  
47    return 0; 
48} 

1// A Naive recursive Java program to find minimum number 
2// operations to convert str1 to str2 
3class EDIST 
4{ 
5    static int min(int x,int y,int z) 
6    { 
7        if (x<=y && x<=z) return x; 
8        if (y<=x && y<=z) return y; 
9        else return z; 
10    } 
11  
12    static int editDist(String str1 , String str2 , int m ,int n) 
13    { 
14        // If first string is empty, the only option is to 
15    // insert all characters of second string into first 
16    if (m == 0) return n; 
17       
18    // If second string is empty, the only option is to 
19    // remove all characters of first string 
20    if (n == 0) return m; 
21       
22    // If last characters of two strings are same, nothing 
23    // much to do. Ignore last characters and get count for 
24    // remaining strings. 
25    if (str1.charAt(m-1) == str2.charAt(n-1)) 
26        return editDist(str1, str2, m-1, n-1); 
27       
28    // If last characters are not same, consider all three 
29    // operations on last character of first string, recursively 
30    // compute minimum cost for all three operations and take 
31    // minimum of three values. 
32    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert 
33                     editDist(str1,  str2, m-1, n),   // Remove 
34                     editDist(str1,  str2, m-1, n-1) // Replace                      
35                   ); 
36    } 
37  
38    public static void main(String args[]) 
39    { 
40        String str1 = "sunday"; 
41        String str2 = "saturday"; 
42   
43        System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) ); 
44    } 
45} 
46/*This code is contributed by Rajat Mishra*/

1# A Naive recursive Python program to fin minimum number 
2# operations to convert str1 to str2 
3def editDistance(str1, str2, m , n): 
4  
5    # If first string is empty, the only option is to 
6    # insert all characters of second string into first 
7    if m==0: 
8         return n 
9  
10    # If second string is empty, the only option is to 
11    # remove all characters of first string 
12    if n==0: 
13        return m 
14  
15    # If last characters of two strings are same, nothing 
16    # much to do. Ignore last characters and get count for 
17    # remaining strings. 
18    if str1[m-1]==str2[n-1]: 
19        return editDistance(str1,str2,m-1,n-1) 
20  
21    # If last characters are not same, consider all three 
22    # operations on last character of first string, recursively 
23    # compute minimum cost for all three operations and take 
24    # minimum of three values. 
25    return 1 + min(editDistance(str1, str2, m, n-1),    # Insert 
26                   editDistance(str1, str2, m-1, n),    # Remove 
27                   editDistance(str1, str2, m-1, n-1)    # Replace 
28                   ) 
29  
30# Driver program to test the above function 
31str1 = "sunday"
32str2 = "saturday"
33print editDistance(str1, str2, len(str1), len(str2)) 
34  
35# This code is contributed by Bhavya Jain 

1// A Naive recursive C# program to 
2// find minimum numberoperations  
3// to convert str1 to str2 
4using System; 
5  
6class GFG 
7{ 
8    static int min(int x, int y, int z) 
9    { 
10        if (x <= y && x <= z) return x; 
11        if (y <= x && y <= z) return y; 
12        else return z; 
13    } 
14  
15    static int editDist(String str1 , String str2 , int m ,int n) 
16    { 
17        // If first string is empty, the only option is to 
18        // insert all characters of second string into first 
19        if (m == 0) return n; 
20          
21        // If second string is empty, the only option is to 
22        // remove all characters of first string 
23        if (n == 0) return m; 
24          
25        // If last characters of two strings are same, nothing 
26        // much to do. Ignore last characters and get count for 
27        // remaining strings. 
28        if (str1[m - 1] == str2[n - 1]) 
29            return editDist(str1, str2, m - 1, n - 1); 
30          
31        // If last characters are not same, consider all three 
32        // operations on last character of first string, recursively 
33        // compute minimum cost for all three operations and take 
34        // minimum of three values. 
35        return 1 + min ( editDist(str1, str2, m, n - 1), // Insert 
36                        editDist(str1, str2, m - 1, n), // Remove 
37                        editDist(str1, str2, m - 1, n - 1) // Replace                      
38                    ); 
39    } 
40      
41    // Driver code 
42    public static void Main() 
43    { 
44        String str1 = "sunday"; 
45        String str2 = "saturday"; 
46        Console.WriteLine( editDist( str1 , str2 , str1.Length,  
47                                                 str2.Length )); 
48    } 
49} 
50  
51// This Code is Contributed by Sam007 

1<?php  
2// A Naive recursive Python program   
3// to find minimum number operations  
4// to convert str1 to str2  
5function editDistance($str1, $str2,  
6                      $m, $n) 
7{  
8    // If first string is empty,  
9    // the only option is to insert. 
10    // all characters of second 
11    // string into first  
12    if ($m == 0) 
13        return $n;  
14  
15    // If second string is empty, 
16    // the only option is to  
17    // remove all characters of  
18    // first string  
19    if ($n == 0)  
20        return $m;  
21  
22    // If last characters of two  
23    // strings are same, nothing  
24    // much to do. Ignore last  
25    // characters and get count  
26    // for remaining strings.  
27    if ($str1[$m - 1] == $str2[$n - 1]) 
28    {  
29        return editDistance($str1, $str2,  
30                            $m - 1, $n - 1);  
31    } 
32      
33    // If last characters are not same,  
34    // consider all three operations on  
35    // last character of first string,  
36    // recursively compute minimum cost  
37    // for all three operations and take  
38    // minimum of three values.  
39  
40    return 1 + min(editDistance($str1, $str2,  
41                                $m, $n - 1), // Insert  
42                   editDistance($str1, $str2,  
43                                $m - 1, $n), // Remove  
44                   editDistance($str1, $str2,  
45                                $m - 1, $n - 1)); // Replace  
46}  
47  
48// Driver Code 
49$str1 = "sunday"; 
50$str2 = "saturday"; 
51echo editDistance($str1, $str2, strlen($str1),  
52                                strlen($str2));  
53  
54// This code is contributed  
55// by Shivi_Aggarwal 
56?> 

1// A Dynamic Programming based C++ program to find minimum 
2// number operations to convert str1 to str2 
3#include<bits/stdc++.h> 
4using namespace std; 
5  
6// Utility function to find the minimum of three numbers 
7int min(int x, int y, int z) 
8{ 
9    return min(min(x, y), z); 
10} 
11  
12int editDistDP(string str1, string str2, int m, int n) 
13{ 
14    // Create a table to store results of subproblems 
15    int dp[m+1][n+1]; 
16  
17    // Fill d[][] in bottom up manner 
18    for (int i=0; i<=m; i++) 
19    { 
20        for (int j=0; j<=n; j++) 
21        { 
22            // If first string is empty, only option is to 
23            // insert all characters of second string 
24            if (i==0) 
25                dp[i][j] = j;  // Min. operations = j 
26  
27            // If second string is empty, only option is to 
28            // remove all characters of second string 
29            else if (j==0) 
30                dp[i][j] = i; // Min. operations = i 
31  
32            // If last characters are same, ignore last char 
33            // and recur for remaining string 
34            else if (str1[i-1] == str2[j-1]) 
35                dp[i][j] = dp[i-1][j-1]; 
36  
37            // If the last character is different, consider all 
38            // possibilities and find the minimum 
39            else
40                dp[i][j] = 1 + min(dp[i][j-1],  // Insert 
41                                   dp[i-1][j],  // Remove 
42                                   dp[i-1][j-1]); // Replace 
43        } 
44    } 
45  
46    return dp[m][n]; 
47} 
48  
49// Driver program 
50int main() 
51{ 
52    // your code goes here 
53    string str1 = "sunday"; 
54    string str2 = "saturday"; 
55  
56    cout << editDistDP(str1, str2, str1.length(), str2.length()); 
57  
58    return 0; 
59} 

1// A Dynamic Programming based Java program to find minimum 
2// number operations to convert str1 to str2 
3class EDIST 
4{ 
5    static int min(int x,int y,int z) 
6    { 
7        if (x <= y && x <= z) return x; 
8        if (y <= x && y <= z) return y; 
9        else return z; 
10    } 
11  
12    static int editDistDP(String str1, String str2, int m, int n) 
13    { 
14        // Create a table to store results of subproblems 
15        int dp[][] = new int[m+1][n+1]; 
16       
17        // Fill d[][] in bottom up manner 
18        for (int i=0; i<=m; i++) 
19        { 
20            for (int j=0; j<=n; j++) 
21            { 
22                // If first string is empty, only option is to 
23                // insert all characters of second string 
24                if (i==0) 
25                    dp[i][j] = j;  // Min. operations = j 
26       
27                // If second string is empty, only option is to 
28                // remove all characters of second string 
29                else if (j==0) 
30                    dp[i][j] = i; // Min. operations = i 
31       
32                // If last characters are same, ignore last char 
33                // and recur for remaining string 
34                else if (str1.charAt(i-1) == str2.charAt(j-1)) 
35                    dp[i][j] = dp[i-1][j-1]; 
36       
37                // If the last character is different, consider all 
38                // possibilities and find the minimum 
39                else
40                    dp[i][j] = 1 + min(dp[i][j-1],  // Insert 
41                                       dp[i-1][j],  // Remove 
42                                       dp[i-1][j-1]); // Replace 
43            } 
44        } 
45   
46        return dp[m][n]; 
47    } 
48  
49      
50  
51    public static void main(String args[]) 
52    { 
53        String str1 = "sunday"; 
54        String str2 = "saturday"; 
55        System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) ); 
56    } 
57}/*This code is contributed by Rajat Mishra*/

1# A Dynamic Programming based Python program for edit 
2# distance problem 
3def editDistDP(str1, str2, m, n): 
4    # Create a table to store results of subproblems 
5    dp = [[0 for x in range(n+1)] for x in range(m+1)] 
6  
7    # Fill d[][] in bottom up manner 
8    for i in range(m+1): 
9        for j in range(n+1): 
10  
11            # If first string is empty, only option is to 
12            # insert all characters of second string 
13            if i == 0: 
14                dp[i][j] = j    # Min. operations = j 
15  
16            # If second string is empty, only option is to 
17            # remove all characters of second string 
18            elif j == 0: 
19                dp[i][j] = i    # Min. operations = i 
20  
21            # If last characters are same, ignore last char 
22            # and recur for remaining string 
23            elif str1[i-1] == str2[j-1]: 
24                dp[i][j] = dp[i-1][j-1] 
25  
26            # If last character are different, consider all 
27            # possibilities and find minimum 
28            else: 
29                dp[i][j] = 1 + min(dp[i][j-1],        # Insert 
30                                   dp[i-1][j],        # Remove 
31                                   dp[i-1][j-1])    # Replace 
32  
33    return dp[m][n] 
34  
35# Driver program 
36str1 = "sunday"
37str2 = "saturday"
38  
39print(editDistDP(str1, str2, len(str1), len(str2))) 
40# This code is contributed by Bhavya Jain 

1// A Dynamic Programming based  
2// C# program to find minimum 
3// number operations to  
4// convert str1 to str2 
5using System; 
6  
7class GFG 
8{ 
9    static int min(int x, int y, int z) 
10    { 
11        if (x <= y && x <= z) return x; 
12        if (y <= x && y <= z) return y; 
13        else return z; 
14    } 
15  
16    static int editDistDP(String str1, String str2, int m, int n) 
17    { 
18        // Create a table to store 
19        // results of subproblems 
20        int [,]dp = new int[m + 1,n + 1]; 
21      
22        // Fill d[][] in bottom up manner 
23        for (int i = 0; i <= m; i++) 
24        { 
25            for (int j = 0; j <= n; j++) 
26            { 
27                // If first string is empty, only option is to 
28                // insert all characters of second string 
29                if (i == 0) 
30                  
31                    // Min. operations = j 
32                    dp[i, j] = j;  
33      
34                // If second string is empty, only option is to 
35                // remove all characters of second string 
36                else if (j == 0) 
37                       
38                     // Min. operations = i 
39                    dp[i,j] = i;  
40      
41                // If last characters are same, ignore last char 
42                // and recur for remaining string 
43                else if (str1[i - 1] == str2[j - 1]) 
44                    dp[i, j] = dp[i - 1, j - 1]; 
45      
46                // If the last character is different, consider all 
47                // possibilities and find the minimum 
48                else
49                    dp[i, j] = 1 + min(dp[i, j - 1], // Insert 
50                                    dp[i - 1, j], // Remove 
51                                    dp[i - 1, j - 1]); // Replace 
52            } 
53        } 
54  
55        return dp[m, n]; 
56    } 
57  
58      
59    // Driver code 
60    public static void Main() 
61    { 
62        String str1 = "sunday"; 
63        String str2 = "saturday"; 
64        Console.Write( editDistDP( str1 , str2 , str1.Length,  
65                                               str2.Length )); 
66    } 
67} 
68// This Code is Contributed by Sam007 

1<?php 
2// A Dynamic Programming based  
3// Python program for edit  
4// distance problem  
5function editDistDP($str1, $str2,  
6                    $m, $n) 
7{  
8// Fill d[][] in bottom up manner  
9for ($i = 0; $i <= $m; $i++)  
10{   
11    for ($j = 0; $j <= $n; $j++)  
12    {  
13  
14        // If first string is empty,  
15        // only option is to insert  
16        // all characters of second string  
17        if ($i == 0)  
18            $dp[$i][$j] = $j ; // Min. operations = j  
19  
20        // If second string is empty,  
21        // only option is to remove  
22        // all characters of second string  
23        else if($j == 0)  
24            $dp[$i][$j] = $i; // Min. operations = i  
25  
26        // If last characters are same,  
27        // ignore last char and recur  
28        // for remaining string  
29        else if($str1[$i - 1] == $str2[$j - 1])  
30            $dp[$i][$j] = $dp[$i - 1][$j - 1]; 
31  
32        // If last character are different,  
33        // consider all possibilities and  
34        // find minimum  
35        else
36        {  
37            $dp[$i][$j] = 1 + min($dp[$i][$j - 1],     // Insert  
38                                  $dp[$i - 1][$j],     // Remove  
39                                  $dp[$i - 1][$j - 1]); // Replace  
40        } 
41    } 
42} 
43return $dp[$m][$n] ; 
44} 
45  
46// Driver Code  
47$str1 = "sunday"; 
48$str2 = "saturday"; 
49  
50echo editDistDP($str1, $str2, strlen($str1),  
51                              strlen($str2)); 
52  
53// This code is contributed  
54// by Shivi_Aggarwal 
55?>