Skip to content
QuantReadySign In
#023easyDynamic Programming

Edit Distance - Ticker Symbol Matching

Part of:Algorithms & Data Structures → 2-D Dynamic Programming

Problem

In a financial data system, ticker symbols sometimes get corrupted during transmission. To identify the closest matching ticker, you need to compute the edit distance (Levenshtein distance) between two strings.

The edit distance is the minimum number of operations required to transform one string into the other. The allowed operations are:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Given two ticker strings s1 and s2, compute their edit distance.

Input Format

  • First line: string s1.
  • Second line: string s2.

Output Format

A single integer representing the minimum edit distance.

Examples

Example 1
Input(First line: string s1.)
AAPL
AAPL
Output
0

The strings are identical, so no edits are needed.

Example 2
Input(First line: string s1.)
GOOGL
GOOGL
Output
0

Already matching.

Constraints

  • •0 ≤ len(s1), len(s2) ≤ 500
  • •Strings consist of uppercase English letters and digits

Execution limits: 2s · 256MB

Loading interactive editor…