# Why can't edit distance be solved as L1 distance?

Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to transform $x$ into $y$.

If $m = \max ( \text{len}(x),\text{len}(y) )$ then padding with appropriate zeroes on the smaller string one can define $x$ and $y$ as both being elements of $\Sigma^m$. Now both $x$ and $y$ are vertices of the cube $\Sigma^m$.

Now isn't $\text{ed}(x,y)$ the shortest distance between $x$ and $y$ in this cube graph? Why isn't edit distance found by finding shortest paths in this cube?

## 1 Answer

Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.

• Why is the edit distance 2 here? – user6818 May 17 '15 at 20:43
• Because you allow insertions and deletions. – André Souza Lemos May 17 '15 at 20:44
• Oh okay - I understand - you want to insert a 1 at the beginning and delete the last 1. – user6818 May 17 '15 at 20:48
• So is there any mathematical notion of distance which corresponds to this notion of "edit distance" ? – user6818 May 17 '15 at 20:48
• That is a new question... or a different version of your question. – André Souza Lemos May 17 '15 at 20:49