📘

Edit Distance for OCR Correction

Problem Statement

In Optical Character Recognition (OCR), text extracted from images often contains errors. Edit Distance (Levenshtein Distance) measures how different two strings are, which helps in:

Spell checking OCR output
Finding the closest dictionary word
Post-processing recognized text

Given two strings source and target, find the minimum number of operations required to convert source to target. The allowed operations are:

Insert a character
Delete a character
Replace a character

Constraints

$0 \leq len(source), len(target) \leq 500$
Strings contain lowercase English letters only

Example:

Input:

source = "kitten", target = "sitting"

Output:

Reasoning:

kitten → sitten (replace k with s) → sittin (replace e with i) → sitting (insert g)

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘