✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-179

Edit Distance Problem

Understand how dynamic programming calculates the minimum number of insertions, deletions, and substitutions needed to transform one string into another.

Explanation

Overview

Edit Distance, commonly called Levenshtein Distance, measures the minimum number of single-character operations required to transform one string into another. The standard version allows insertion, deletion, and substitution, each with a cost of one.

Key concepts

Insertion; Deletion; Substitution; String prefix states; Minimum-cost optimization

Variables

X: The original string.; Y: The target string.; i: The number of characters considered from X.; j: The number of characters considered from Y.; dp[i][j]: The minimum edit cost for transforming the first i characters of X into the first j characters of Y.

Complexity

tabulation: O(mn) time and O(mn) space.; spaceOptimized: O(mn) time and O(min(m,n)) space.; variables: m and n are the lengths of the source and target strings.

Example

source: kitten; target: sitting; operations: Replace k with s.; Replace e with i.; editDistance: 3; explanation: Three operations are sufficient to transform kitten into sitting, and no solution can use fewer operations under the standard cost model.

Pseudocode

function editDistance(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1)
for i = 0 to m:
dp[i][0] = i
for j = 0 to n:
dp[0][j] = j
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[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]

Applications

Spell checking.; Autocomplete and text correction.; DNA sequence comparison.; Plagiarism and similarity analysis.; Natural language processing.

Variables

X

The original string.

Y

The target string.

I

The number of characters considered from X.

J

The number of characters considered from Y.

Dp[i][j]

The minimum edit cost for transforming the first i characters of X into the first j characters of Y.

Example or application

Source

kitten

Target

sitting

Operations

  • Replace k with s.

  • Replace e with i.

  • Insert g at the end.

Edit Distance

3

Explanation

Three operations are sufficient to transform kitten into sitting, and no solution can use fewer operations under the standard cost model.

Definition

Edit Distance, commonly called Levenshtein Distance, measures the minimum number of single-character operations required to transform one string into another. The standard version allows insertion, deletion, and substitution, each with a cost of one.

Mathematical Representation

If X[i-1] = Y[j-1], dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Approaches

Recursive

Considers insertion, deletion, and substitution possibilities for the final characters.

Memoization

Stores the minimum edit cost for each pair of string prefixes.

Tabulation

Builds a two-dimensional table using smaller prefix transformations.

Space Optimized

Stores only the previous and current rows when only the distance is required.

Pseudocode

function editDistance(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1)
for i = 0 to m:
dp[i][0] = i
for j = 0 to n:
dp[0][j] = j
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[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]

Complexity

Tabulation

O(mn) time and O(mn) space.

Space Optimized

O(mn) time and O(min(m,n)) space.

Variables

m and n are the lengths of the source and target strings.

Key Concepts

  • Insertion

  • Deletion

  • Substitution

  • String prefix states

  • Minimum-cost optimization

Advantages

  • Provides a quantitative measure of string similarity.

  • Finds the minimum number of standard edit operations.

  • Can reconstruct an optimal sequence of edits.

  • Can be extended to weighted edit costs.

Limitations

  • The standard algorithm requires O(mn) time.

  • Large strings can require substantial memory.

  • The result depends on the allowed operations and their assigned costs.

  • A small edit distance does not always imply that two texts have the same meaning.

Applications

  • Spell checking.

  • Autocomplete and text correction.

  • DNA sequence comparison.

  • Plagiarism and similarity analysis.

  • Natural language processing.

Related Topics

  • Longest Common Subsequence

  • String Matching

  • Dynamic Programming

  • Sequence Alignment

Practice Question

What is the standard Levenshtein edit distance between CAT and CUT?

Practice Answer

1, because only A needs to be substituted with U.

Learning Objectives

  • Explain the central idea and purpose of edit distance problem.

  • Identify the assumptions, inputs, and conditions relevant to edit distance problem.

  • Evaluate an application of edit distance problem for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures