Edit Distance - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/edit-distance

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/edit-distance

Repovive

Edit Distance - Algorithm Tutorial | Repovive | Repovive

Implementation

Here's the complete pseudocode:

function editDistance(s, t):
    m = length(s)
    n = length(t)
    dp = new array[m + 1][n + 1]
    
    for i from 0 to m:
        dp[i][0] = i
    for j from 0 to n:
        dp[0][j] = j
    
    for i from 1 to m:
        for j from 1 to n:
            if s[i - 1] == t[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]

Edit Distance Algorithm Tutorial

Introduction

Practice this Algorithm

Related Algorithms

Intuition

DP State & Transition

Implementation

Complexity & Optimization