[Verse 1]
Two strings sitting side by side, gotta find the cost to transform
One becomes the other through operations, that's the norm
Insert a character, delete one out, substitute what's wrong
Minimum steps to make them match, been computing all along
Dynamic programming table, bottom up we climb
Each cell holds the answer to a smaller problem's rhyme
If characters are equal, take diagonal for free
Otherwise add one to the minimum of three
[Chorus]
Edit distance, Levenshtein's the name
Three operations in this coding game
Insert, delete, substitute the letters
Dynamic programming makes it better
Minimum steps from A to B
That's the metric, can't you see
Edit distance, edit distance
Measuring string resistance
[Verse 2]
Matrix filled with numbers, rows and columns aligned
Source string on the left side, target string defined
Across the top we place it, base cases initialized
Zero to length transformations, foundation crystallized
Compare each character pair, decision time has come
Equal means diagonal, no operation sum
Different means we calculate, three paths we explore
Add one to minimum, that's what matrices are for
[Chorus]
Edit distance, Levenshtein's the name
Three operations in this coding game
Insert, delete, substitute the letters
Dynamic programming makes it better
Minimum steps from A to B
That's the metric, can't you see
Edit distance, edit distance
Measuring string resistance
[Bridge]
Applications everywhere, spell check and DNA
Plagiarism detection, finding similarity
Time complexity quadratic, space can be optimized
Rolling array technique, memory's been revised
Weighted versions possible, costs don't have to be one
Damerau adds transposition when the coding's done
[Verse 3]
Recurrence relation clear, three cases to decide
Deletion from the source, insertion to the side
Substitution changes both, diagonal with cost
Minimum of all three paths, efficiency's not lost
Fill the table row by row, left to right we go
Bottom right corner holds the answer that we know
String alignment algorithms, this is where they start
Edit distance computation, truly computational art
[Chorus]
Edit distance, Levenshtein's the name
Three operations in this coding game
Insert, delete, substitute the letters
Dynamic programming makes it better
Minimum steps from A to B
That's the metric, can't you see
Edit distance, edit distance
Measuring string resistance
[Outro]
From kitten to sitting, three steps will do
Insert S, substitute K, computation's true
Edit distance mastered, algorithm's complete
Levenshtein's legacy, can't accept defeat