Knowledge Base | Daily Notes

Edit Distance algorithm

Aug 30, 20243 min read

  • Levenshtein distance algorithm

Problem statement

Given two strings str1 and str2 of length M and N respectively and below operations that can be performed on str1. Find the minimum number of edits (operations) to convert ‘str1‘ into ‘str2‘.

Operation 1 (INSERT): Insert any character before or after any index of str1 Operation 2 (REMOVE): Remove a character of str1 Operation 3 (Replace): Replace a character at any index of str1 with some other character. Note: All of the above operations are of equal cost.

Examples:

Input: str1 = “geek”, str2 = “gesek” Output: 1 Explanation: We can convert str1 into str2 by inserting a ‘s’ between two consecutive ‘e’ in str2.

Notes

Code

Javascript

class Solution {
  // space optimization
  editDistance(s, t) {
    const n = s.length;
    const m = t.length;
 
    const prev = new Array(m + 1).fill(0);
    const curr = new Array(m + 1).fill(0);
 
    for (let j = 0; j <= m; j++) {
      prev[j] = j;
    }
 
    for (let i = 1; i <= n; i++) {
      curr[0] = i;
      for (let j = 1; j <= m; j++) {
        if (s[i - 1] === t[j - 1]) {
          curr[j] = prev[j - 1];
        } else {
          const mn = Math.min(1 + prev[j], 1 + curr[j - 1]);
          curr[j] = Math.min(mn, 1 + prev[j - 1]);
        }
      }
      prev.splice(0, m + 1, ...curr);
    }
 
    return prev[m];
  }
}
 
const s = "saturday";
const t = "sunday";
 
const ob = new Solution();
const ans = ob.editDistance(s, t);
console.log(ans);

Pythonspace_complexity optimized

 
class Solution:
    def editDistance(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)
 
        prev = [j for j in range(m+1)]
        curr = [0] * (m+1)
 
        for i in range(1, n+1):
            curr[0] = i
            for j in range(1, m+1):
                if s[i-1] == t[j-1]:
                    curr[j] = prev[j-1]
                else:
                    mn = min(1 + prev[j], 1 + curr[j-1])
                    curr[j] = min(mn, 1 + prev[j-1])
            prev = curr.copy()
 
        return prev[m]
 
 
s = "saturday"
t = "sunday"
 
ob = Solution()
ans = ob.editDistance(s, t)
print(ans)

Bottom_Up approach

 
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])    # Replace
 
    return dp[m][n]
 
 
# Driver code
str1 = "sunday"
str2 = "saturday"

Applications

  • Spell Checking and Auto-Correction
  • DNA Sequence Alignment
  • Plagiarism Detection
  • NLP
  • Version Control Systems, Git
  • String Matching

Graph View

Backlinks