Levenshtein Part 2: Dynamic Programming

Proceeding from the earlier post on the same topic, we have the following code for a Dynamic Programming bottom-up approach to the Levenshtein “Edit Distance” algorithm where all the weights are simply “1” for insert, delete, substitute operations. Note that this would be also referred to the “tabular” approach as well since we fill up a matrix as we go along.

In a later post, we would attempt to reduce the space requirement from O(m.n) to a constant. In another post, we would provide a way to configure the weights and thereby providing weighted edges to the DAG.

 

And the test code:

Leave a Reply

Your email address will not be published. Required fields are marked *

     

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">