ThomazL's blog

By ThomazL, history, 9 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Editorial of a problem that asks us to implement the same thing.

Problem Link