Computer Science & Data Science · Data structures and algorithms

Levenshtein edit distance

Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.

AdvancedUniversity/collegeBachelor foundationsSubject specialization

Create flashcards or a quiz I already have an account

Free to browse · flashcards or a multiple-choice quiz · import from Essential

Formula

D (i, j) = min {D (i - 1, j) + 1, D (i, j - 1) + 1, D (i - 1, j - 1) + [a_{i} \neq = b_{j}]}

integer number of edit operations; dimensionless

Variables & units

Variables & units
Symbol	Meaning	Unit
$D(i,j)$	Distance between prefixes of lengths i and j	number of operations
$aᵢ,bⱼ$	Characters at positions i and j	characters
[a_i≠b_j]	One when characters differ, otherwise zero	dimensionless

LaTeX

D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}

QUANTA STUDYquanta-study.de

Derivation & background

The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces space to O(min(m,n)) but does not retain an edit path without extra methods. Ordinary Levenshtein distance does not count transposition as one operation.

Exam blueprint

Validity range

Derivation steps

Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.

1Read the relation from its definition: D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}.
2Identify the input, requested output and assumptions of the relation.
3The strings “Haus” and “Maus” differ by one substitution, H→M, so their edit distance is 1.

Rearrangements

Defining relation

D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}

The equation states the defining relation within its stated domain.

Task variant

Use the example for Levenshtein edit distance to explain which inputs determine the requested output.

The example connects concrete inputs to its result.
Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.
The relation applies only under its stated assumptions.

Common mistakes

Applying the relation to a different case without checking its stated assumptions.

Check the validity range before substituting values: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces.

Exam context

Typo correction, fuzzy search, DNA sequences and string matching.

Formula cluster

Data structures and algorithms

Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.

dH(x,y) = Zahl unterschiedlicher Stellen

Hamming distance between bit strings

f(n) ∈ O(g(n))

Big-O notation (asymptotic upper bound)

w(t,d) = TF(t,d) · log(N/df(t))

TF-IDF term weighting

Worked example

The strings “Haus” and “Maus” differ by one substitution, H→M, so their edit distance is 1.

Applications

Typo correction, fuzzy search, DNA sequences and string matching.

How do you calculate with Levenshtein edit distance?

Here is how to work through a typical Levenshtein edit distance (Minimum aus Einfügen, Löschen, Ersetzen) task step by step:

1
Task
Use the example for Levenshtein edit distance to explain which inputs determine the requested output.
Solution path
1. The example connects concrete inputs to its result.
2. Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.
3. The relation applies only under its stated assumptions.

Frequently asked questions about Levenshtein edit distance

What does Levenshtein edit distance describe?+

The relation D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\} summarizes Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another. Read it as a model for defined quantities, not as an automatic claim about every real situation. In the example The strings “Haus” and “Maus” differ by one substitution, H→M, so their edit distance is 1., symbols are connected to concrete values and the result is interpreted in context. Validity limit: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces Source: NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

How should I work through a calculation?+

First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example The strings “Haus” and “Maus” differ by one substitution, H→M, so their edit distance is 1. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces Source: NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

Which assumption must I keep in mind?+

The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces Source: NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

Which units and quantities are involved?+

The stated units are: integer number of edit operations; dimensionless. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces Source: NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

When is comparison with hamming-distanz-bitfolgen and big-o-notation useful?+

Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source NIST Dictionary of Algorithms and Data Structures, Levenshtein distance. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: The dynamic recurrence considers the final character pair and selects insertion, deletion or substitution. Initialize D(i,0)=i and D(0,j)=j. The standard algorithm takes O(mn) time and O(mn) space; row-wise computation reduces Source: NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

Quanta exam set

Curated exam set for "Levenshtein edit distance":

Question (front)

Which formula describes Levenshtein edit distance?

Answer in your set

Question (front)

How do you rearrange Levenshtein edit distance for Defining relation?

Answer in your set

Question (front)

Which common mistake happens with Levenshtein edit distance?

Answer in your set

+ 7 more cards: units, variables, derivation, example, exam task

The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.

Create flashcards or a quiz I already have an account

Subject references and further reading

This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.

[1]NIST Dictionary of Algorithms and Data Structures, Levenshtein distance.

More formulas: Algorithms, number representation and cryptography

x=-b_{N-1}2^{N-1}+\sum_{i=0}^{N-2}b_i2^i

Two’s-complement signed integer

T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1)

Divide-and-conquer runtime recurrence

x=(-1)^s\begin{cases}(1+f)2^{E-b},&0<E<2^w-1\\f2^{1-b},&E=0\end{cases}

IEEE 754 floating-point representation and rounding

\neg(A\land B)=\neg A\lor\neg B,\quad\neg(A\lor B)=\neg A\land\neg B

Boolean algebra identities and De Morgan laws

Spaced-repetition apps

Compare scheduling workflows

Study evidence

Read methods, results and limits

Compare flashcard apps

FSRS support and study features

Create a formula exam set

From Essential in Quanta

Retain Levenshtein edit distance for exams

Create a curated FSRS exam set for Minimum aus Einfügen, Löschen, Ersetzen: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.

Create flashcards or a quiz Already registered? Continue directly

Curated formula set · LaTeX · FSRS spaced repetition · import from Essential

Quanta Study editorial team

Levenshtein edit distance

Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.

AdvancedUniversity/collegeBachelor foundationsSubject specialization

Free to browse · flashcards or a multiple-choice quiz · import from Essential

Symbol

Meaning

Unit

D(i,j)

Distance between prefixes of lengths i and j

number of operations

aᵢ,bⱼ

Characters at positions i and j

characters

[a_i≠b_j]

One when characters differ, otherwise zero

dimensionless

Derivation & background

Exam blueprint

Validity range

Derivation steps

Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.

1Read the relation from its definition: D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}.
2Identify the input, requested output and assumptions of the relation.
3The strings “Haus” and “Maus” differ by one substitution, H→M, so their edit distance is 1.

How do you calculate with Levenshtein edit distance?

Here is how to work through a typical Levenshtein edit distance (Minimum aus Einfügen, Löschen, Ersetzen) task step by step:

Task

Use the example for Levenshtein edit distance to explain which inputs determine the requested output.

Solution path

The example connects concrete inputs to its result.
Levenshtein distance is the minimum number of insertions, deletions and substitutions needed to transform one string into another.
The relation applies only under its stated assumptions.

Frequently asked questions about Levenshtein edit distance

What does Levenshtein edit distance describe?+

How should I work through a calculation?+

Which assumption must I keep in mind?+

Which units and quantities are involved?+

When is comparison with hamming-distanz-bitfolgen and big-o-notation useful?+

Retain Levenshtein edit distance for exams

Create a curated FSRS exam set for Minimum aus Einfügen, Löschen, Ersetzen: formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.

Curated formula set · LaTeX · FSRS spaced repetition · import from Essential