Commitd792636

authored

Added Levenshtein Distance Algorithm (TheAlgorithms#263)

1 parentcfdf6fa commitd792636Copy full SHA for d792636

File tree

+49

-0

lines changed

+49

-0

lines changed

Lines changed: 49 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,49 @@`
	`1`	`+/**`
	`2`	`+ * A Dynamic Programming based solution for calculation of the Levenshtein Distance`
	`3`	`+ * https://en.wikipedia.org/wiki/Levenshtein_distance`
	`4`	`+ */`
	`5`	`+`
	`6`	`+functionminimum(a,b,c){`
	`7`	`+if(a<b&&a<c){`
	`8`	`+returna`
	`9`	`+}elseif(b<a&&b<c){`
	`10`	`+returnb`
	`11`	`+}else{`
	`12`	`+returnc`
	`13`	`+}`
	`14`	`+}`
	`15`	`+`
	`16`	`+functioncostOfSubstitution(x,y){`
	`17`	`+returnx===y ?0 :1`
	`18`	`+}`
	`19`	`+`
	`20`	`+functioncalculate(x,y){`
	`21`	`+constdp=newArray(x.length+1)`
	`22`	`+for(leti=0;i<x.length+1;i++){`
	`23`	`+dp[i]=newArray(y.length+1)`
	`24`	`+}`
	`25`	`+`
	`26`	`+for(leti=0;i<x.length+1;i++){`
	`27`	`+for(letj=0;j<y.length+1;j++){`
	`28`	`+if(i===0){`
	`29`	`+dp[i][j]=j`
	`30`	`+}elseif(j===0){`
	`31`	`+dp[i][j]=i`
	`32`	`+}else{`
	`33`	`+dp[i][j]=minimum(dp[i-1][j-1]+costOfSubstitution(x.charAt(i-1),y.charAt(j-1)),dp[i-1][j]+1,dp[i][j-1]+1)`
	`34`	`+}`
	`35`	`+}`
	`36`	`+}`
	`37`	`+`
	`38`	`+returndp[x.length][y.length]`
	`39`	`+}`
	`40`	`+`
	`41`	`+functionmain(){`
	`42`	`+constx=''// enter your string here`
	`43`	`+consty=''// enter your string here`
	`44`	`+`
	`45`	`+console.log('Levenshtein distance between '+x+' and '+y+' is: ')`
	`46`	`+console.log(calculate(x,y))`
	`47`	`+}`
	`48`	`+`
	`49`	`+main()`

Comments

(0)