Edit Distance Problem Levenshtein in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Edit Distance (Levenshtein distance) between two strings?

It is the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into the other.

beginner

Which operations are allowed in calculating Levenshtein distance?

Insertion, deletion, and substitution of a single character.

intermediate

What is the base case when using dynamic programming to compute Levenshtein distance?

When one string is empty, the distance is the length of the other string (all insertions or deletions).

intermediate

How does the dynamic programming table for Levenshtein distance get filled?

Each cell represents the minimum edit distance between prefixes of the two strings, calculated using values from neighboring cells representing smaller prefixes.

beginner

Why is Levenshtein distance useful in real life?

It helps in spell checking, DNA sequence analysis, and natural language processing by measuring how similar two strings are.

Which of the following is NOT an allowed operation in Levenshtein distance?

A Transposition

B Deletion

C Substitution

D Insertion

Levenshtein distance allows insertion, deletion, and substitution, but not transposition (swapping two adjacent characters).

What is the Levenshtein distance between "cat" and "cut"?

A 2

B 1

C 3

D 0

Only one substitution (a -> u) is needed, so the distance is 1.

If one string is empty and the other has length 5, what is the Levenshtein distance?

A 0

B 1

C 5

D Cannot be determined

All 5 characters must be inserted or deleted, so the distance is 5.

In dynamic programming for Levenshtein distance, what does each cell in the table represent?

A Minimum edit distance between prefixes of the two strings

B Number of substitutions only

C Length of the longer string

D Number of insertions only

Each cell stores the minimum edit distance between prefixes of the two strings up to that point.

Which real-life application uses Levenshtein distance?

A Rendering graphics

B Sorting numbers

C Calculating factorial

D Spell checking

Spell checking uses Levenshtein distance to find words close to a misspelled word.

Explain how dynamic programming helps compute the Levenshtein distance between two strings.

Think about how you compare smaller parts of the strings step by step.

Describe the three operations allowed in the Edit Distance Problem and how each affects the strings.

Imagine changing one word into another by editing letters.