If this is the case of Levenshtein Distance, I think substitution costs 2 instead of 1.

for (let j = 1; j <= b.length; j += 1) {
for (let i = 1; i <= a.length; i += 1) {
const indicator = a[i - 1] === b[j - 1] ? 0 : 1;

distanceMatrix[j][i] = Math.min(
distanceMatrix[j][i - 1] + 1, // deletion
…

Dynamic Programming vs Divide-and-Conquer

5.7K

Oleksii Trekhleb

Akhil Gautam

1 min readJun 21, 2018

If this is the case of Levenshtein Distance, I think substitution costs 2 instead of 1.

Correct me if I am wrong.

Written by Akhil Gautam

33 Followers

I am a fullStack developer building things at BigBinary using Ruby on Rails and React.js .

Help
Status
Writers
Blog
Careers
Privacy
Terms
About
Text to speech
Teams