Improved Edit Distance [Help]

Revision en1, by ThomazL, 2016-02-19 18:48:35

Hi guys,

I've read about edit distance problem. Studying this Wikipedia article. It's described one variation problem "one of which takes two strings and a maximum edit distance s, and returns min(s, d)". But i don't understand idea to solve it. Can somebody help me to understand it: "It achieves this by only computing and storing a part of the dynamic programming table around its diagonal."???

Thanks alot for help.

Tags help, dp, algorihm, hit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ThomazL 2016-02-19 18:48:35 503 Initial revision (published)