Edit Distance Problem Levenshtein in DSA Typescript - Build from Scratch

Edit Distance Problem Levenshtein

📖 Scenario: You are building a simple text comparison tool that helps find how different two words are. This is useful in spell checkers or search suggestions.

🎯 Goal: Build a program that calculates the Levenshtein edit distance between two words. This distance tells how many single-letter changes (insertions, deletions, or substitutions) are needed to change one word into the other.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D array to store distances

Use nested loops to fill the distance table using Levenshtein logic

Print the final edit distance number

💡 Why This Matters

🌍 Real World

Spell checkers, search engines, and text correction tools use edit distance to suggest correct words or find similar strings.

💼 Career

Understanding dynamic programming and string algorithms is important for software engineers working on text processing, search, and natural language processing.

1

Create the two words to compare

Create two string variables called word1 and word2 with the exact values "kitten" and "sitting" respectively.

DSA Typescript

# Your code here

Hint

Use const to create variables and assign the exact strings.

2

Create the 2D array to store distances

Create a 2D array called dp with dimensions word1.length + 1 by word2.length + 1. Initialize it with zeros. Then fill the first row with numbers from 0 to word2.length and the first column with numbers from 0 to word1.length.

DSA Typescript

const word1: string = "kitten";
const word2: string = "sitting";
// Your code here

Hint

Use Array.fill and map to create the 2D array. Use loops to fill first row and column.

3

Fill the distance table using Levenshtein logic

Use nested for loops with variables i from 1 to word1.length and j from 1 to word2.length. Inside, if word1[i - 1] equals word2[j - 1], set dp[i][j] to dp[i - 1][j - 1]. Otherwise, set dp[i][j] to 1 plus the minimum of dp[i - 1][j], dp[i][j - 1], and dp[i - 1][j - 1].

DSA Typescript

const word1: string = "kitten";
const word2: string = "sitting";

const dp: number[][] = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));

for (let i = 0; i <= word1.length; i++) {
    dp[i][0] = i;
}
for (let j = 0; j <= word2.length; j++) {
    dp[0][j] = j;
}

// Your code here

Hint

Use nested loops and compare characters at i - 1 and j - 1. Use Math.min to find the smallest cost.

4

Print the final edit distance

Print the value of dp[word1.length][word2.length] which is the Levenshtein edit distance between word1 and word2.

DSA Typescript

const word1: string = "kitten";
const word2: string = "sitting";

const dp: number[][] = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));

for (let i = 0; i <= word1.length; i++) {
    dp[i][0] = i;
}
for (let j = 0; j <= word2.length; j++) {
    dp[0][j] = j;
}

for (let i = 1; i <= word1.length; i++) {
    for (let j = 1; j <= word2.length; j++) {
        if (word1[i - 1] === word2[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1];
        } else {
            dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        }
    }
}

// Your code here

Hint

Print the bottom-right value of the dp table to get the edit distance.