Secondly, it is possible to do better than the Wagner-Fischer algorithm in certain cases. I figured this out myself and was about to write a paper on it when I realized that other researchers had beat me to it by a couple of decades.
If the two strings are equal you can establish that the edit distance is 0 in linear time, obviously. If you consider how the algorithm fills out the square down the diagonal you'll see that if there's only a one-letter difference you only actually need to fill out small parts of the grid around that difference.
This is generalizable, so the complexity actually depends on the distance between the strings.