Wagner Fischer Algorithm and the Empty String In the Wagner Fischer algorithm to calculate the Levenshtein distance for two input strings, the first step is to compare each input string with the empty string for each input. Why is this step necessary? Is the purpose simply to keep the algorithm consistent when checking the strings for matches and mismatches to determine the distance between two prefixes? 

Thanks!
The Wagner&ndash;Fischer is a dynamic programming algorithm. You can think of a dynamic programming algorithm like a recursion. Every recursion needs a base case (like in induction). In this case, the base case is prefixes of length zero. We could also use prefixes of length one as a base case, but the simplest implementation of the algorithms starts with prefixes of length zero.

The prefix zero case can actually happen, for example when both strings have disjoint sets of letters.