Edit Distance in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
#include <string.h>
int min(int a, int b, int c) {
    if (a <= b && a <= c) return a;
    else if (b <= a && b <= c) return b;
    else return c;
}
int editDistance(char s1[], char s2[]) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m+1][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 if (s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
        }
    }
    return dp[m][n];
}
int main() {
    char s1[]="kitten", s2[]="sitting";
    printf("Edit Distance: %d\n", editDistance(s1,s2));
    return 0;
}

C Output

Edit Distance: 3

C++ Program

#include <iostream>
#include <vector>
using namespace std;
int min3(int a, int b, int c){ return min(a, min(b, c)); }
int editDistance(string s1, string s2){
    int m=s1.size(), n=s2.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 if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=1+min3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
        }
    }
    return dp[m][n];
}
int main(){
    string s1="kitten", s2="sitting";
    cout<<"Edit Distance: "<<editDistance(s1,s2)<<endl;
}

C++ Output

Edit Distance: 3

JAVA Program

class Main {
    static int min3(int a,int b,int c){ return Math.min(a, Math.min(b,c)); }
    static int editDistance(String s1,String s2){
        int m=s1.length(), n=s2.length();
        int dp[][]=new int[m+1][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 if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=1+min3(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
            }
        }
        return dp[m][n];
    }
    public static void main(String[] args){
        String s1="kitten", s2="sitting";
        System.out.println("Edit Distance: "+editDistance(s1,s2));
    }
}

JAVA Output

Edit Distance: 3

Python Program

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if i==0:
                dp[i][j]=j
            elif j==0:
                dp[i][j]=i
            elif s1[i-1]==s2[j-1]:
                dp[i][j]=dp[i-1][j-1]
            else:
                dp[i][j]=1+min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print("Edit Distance:", edit_distance("kitten", "sitting"))

Python Output

Edit Distance: 3

Deep Explanation of Edit Distance

Example

Let us consider the words "kitten" and "sitting". The edit distance is 3. We can convert "kitten" to "sitting" with these three operations:

Replace 'k' with 's' → "sitten"

Replace 'e' with 'i' → "sittin"

Append 'g' at the end → "sitting"

So, we require 3 edits.

Real-Life Analogy

Suppose you wrote a message "kitten" but actually wanted to write "sitting". To edit it, you need to do some editing on the text: inserting new characters, replacing existing ones, or removing surplus ones. The edit distance is just the minimum amount of effort to correct the word. It's like finding how many little steps you have to take in order to arrive at your destination when you're a bit off track.

Why It Matters

Edit distance is used in some of the most common algorithms in natural language processing (NLP), spell checking, autocorrect, DNA sequence comparison, and even plagiarism checking. For instance, when Google proposes corrections such as "Did you mean sitting?" when you type "kitten" into search, it is employing edit distance (or its versions such as Damerau-Levenshtein).

Learning Insights

This exercise is introducing you to dynamic programming (DP), an effective method for solving problems with overlapping subproblems. The DP method fills a 2D table where each cell contains the edit distance between substrings of s1 and s2. By dividing the large problem into subproblems and finding their results, we have efficiency that brute force does not. Brute force would attempt all the possible edits, but DP provides a structured and optimized method.

Interview Relevance

Edit distance is a traditional interview question for Google, Microsoft, and Amazon since it challenges both optimization and algorithm design skills. It tests if you know recursion, dynamic programming, and string manipulation. Interviewers sometimes take it further by asking you to regenerate the sequence of edits instead of only the count. Knowing how to explain practical applications such as autocorrect or DNA matching strengthens your answer.

Real-World Application

In bioinformatics, researchers employ edit distance to quantify how closely two DNA strands are. For example, comparing a normal DNA strand with a mutated one can indicate how many gene modifications are needed. Likewise, in version control tools such as Git, file difference comparisons employ analogous ideas. Even music and audio recognition software occasionally employ variations of edit distance to match patterns.

SEO-Optimized Conclusion

Knowledge of edit distance is critical for computer programmers who work in areas such as string algorithms, natural language processing, and machine learning procedures. Through the process of calculating the minimum number of deletions, insertions, and substitutions, students develop an appreciation for dynamic programming and its applications. This idea is not just helpful in study preparation and coding interviews but is also the foundation of contemporary technologies like autocorrect, spell-check, DNA sequence alignment, and search engine predictions. Edit distance mastery will improve your algorithmic problem-solving skill and equip you for real-world projects and competitive programming problems.