Commitea7d06a

authored

tests: Levenshtein Distance (dynamic programming solution) (TheAlgorithms#1114)

1 parent9528c71 commitea7d06aCopy full SHA for ea7d06a

File tree

+28

-5

lines changed

+28

-5

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -91,7 +91,7 @@ npm test`
`91`	`91`	`If you want save some time and just run a specific test:`
`92`	`92`
`93`	`93`	```shell
`94`		`-#this will run any test file where the filenamematches "koch"`
	`94`	`+#This will run any test file where the filenamecontains "koch" (no need to specify folder path)`
`95`	`95`	`npmtest -- koch`
`96`	`96`	```
`97`	`97`

Lines changed: 8 additions & 4 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,10 @@`
`1`	`1`	`/**`
`2`		`- * A Dynamic Programming based solution for calculation of the Levenshtein Distance`
`3`		`- * https://en.wikipedia.org/wiki/Levenshtein_distance`
	`2`	`+ *@function calculateLevenshteinDp`
	`3`	`+ *@description A Dynamic Programming based solution for calculation of the Levenshtein Distance.`
	`4`	`+ *@param {String} x - Word to be converted.`
	`5`	`+ *@param {String} y - Desired result after operations.`
	`6`	`+ *@return {Integer} The Levenshtein distance between x and y.`
	`7`	`+ *@see [Levenshtein_distance](https://en.wikipedia.org/wiki/Levenshtein_distance)`
`4`	`8`	`*/`
`5`	`9`
`6`	`10`	`functionminimum(a,b,c){`
`@@ -18,7 +22,7 @@ function costOfSubstitution (x, y) {`
`18`	`22`	`}`
`19`	`23`
`20`	`24`	`// Levenshtein distance between x and y`
`21`		`-functioncalculate(x,y){`
	`25`	`+functioncalculateLevenshteinDp(x,y){`
`22`	`26`	`constdp=newArray(x.length+1)`
`23`	`27`	`for(leti=0;i<x.length+1;i++){`
`24`	`28`	`dp[i]=newArray(y.length+1)`
`@@ -39,4 +43,4 @@ function calculate (x, y) {`
`39`	`43`	`returndp[x.length][y.length]`
`40`	`44`	`}`
`41`	`45`
`42`		`-export{calculate}`
	`46`	`+export{calculateLevenshteinDp}`

Lines changed: 19 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,19 @@`
	`1`	`+import{calculateLevenshteinDp}from'../LevenshteinDistance'`
	`2`	`+`
	`3`	`+test('Should return the distance counting additions and removals',()=>{`
	`4`	`+constfrom='kitten'`
	`5`	`+constto='sitting'`
	`6`	`+expect(calculateLevenshteinDp(from,to)).toBe(3)`
	`7`	`+})`
	`8`	`+`
	`9`	`+test('Should return the distance based on replacements in the middle of the strings',()=>{`
	`10`	`+constfrom='book'`
	`11`	`+constto='back'`
	`12`	`+expect(calculateLevenshteinDp(from,to)).toBe(2)`
	`13`	`+})`
	`14`	`+`
	`15`	`+test('Should return the distance for strings with different length',()=>{`
	`16`	`+constfrom='sunday'`
	`17`	`+constto='saturday'`
	`18`	`+expect(calculateLevenshteinDp(from,to)).toBe(3)`
	`19`	`+})`

Comments

(0)