#0245

Edit Distance

HardDSA40 min25 XP

Problem

Given two strings a and b, return the minimum number of single-character insert, delete, or replace operations needed to turn a into b.

Why This Matters

Edit distance is the practical DP behind spell-checking, fuzzy matching, and many text similarity systems.

Function Signature

def edit_distance(a, b):

Examples

Example 1

Inputa = "horse", b = "ros"

Output3

One optimal path is replace h with r, delete r, delete e.

Constraints

Return the exact requested value.
Handle empty or small inputs when the prompt allows them.
Prefer the target DSA pattern over brute force when the input can grow.

CodePython

def edit_distance(a, b):
    """
    Input example: a = "horse", b = "ros"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

def edit_distance(a, b):
    """
    Input example: a = "horse", b = "ros"
    Return: 3
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return 0

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Classic edit distance

Inputhorse to ros

Expected3

Three edits are enough and fewer are impossible.

Insertions only

Input"" to "abc"

Expected3

Build the target with three inserts.

Hidden Test Categories

identical stringsreplacement-heavy casedelete-heavy case