#023easyDynamic Programming
Edit Distance - Ticker Symbol Matching
Time Limit: 2sMemory: 256MB
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:
- Insert a character
- Delete a character
- 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
Loading interactive editor…