30. Edit Distance

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large search, messaging, or recommendation platform needs to measure how similar two text strings are. This is useful for:

• typo tolerant search suggestions
• matching user queries to known products
• detecting near-duplicate content
• comparing user names across systems
• ranking results based on string similarity

The platform receives two strings word1 and word2.
It needs to compute the minimum number of editing operations required to convert word1 into word2.

Allowed operations are:

• insert a character
• delete a character
• replace a character

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

Input Format

• word1: a string
• word2: a string

Output Format

• A single integer representing the minimum edit distance

Examples

Constraints

• 0 <= word1.length, word2.length <= 5,000
• word1 and word2 consist of lowercase English letters only