## levDistance(s, t)

##### Last updated March 15, 2004

**Version:** 1 |
**Requires:** CF5 |
**Library:** StrLib

**Description:**

Computes the Levenshtein distance between two strings which is defined as the number of replacements, insertions or deletions necessary to transform the first string into the second.
Ported from the Java version at http://www.merriampark.com/ld.htm

**Return Values:**

Returns a number.

**Example:**

```
<cfoutput>#levDistance("first string", "second string")#</cfoutput>
<!--- should output 6 --->
```

**Parameters:**

Name | Description | Required |
---|---|---|

s | First string. | Yes |

t | Second string. | Yes |

**Full UDF Source: **

```
/**
* Computes the Levenshtein distance between two strings.
*
* @param s First string. (Required)
* @param t Second string. (Required)
* @return Returns a number.
* @author Nicholas Zographos (nicholas@nezen.net)
* @version 1, March 15, 2004
*/
function levDistance(s,t) {
var d = ArrayNew(2);
var i = 1;
var j = 1;
var s_i = "A";
var t_j = "A";
var cost = 0;
var n = len(s)+1;
var m = len(t)+1;
d[n][m]=0;
if (n is 1) {
return m;
}
if (m is 1) {
return n;
}
for (i = 1; i lte n; i=i+1) {
d[i][1] = i-1;
}
for (j = 1; j lte m; j=j+1) {
d[1][j] = j-1;
}
for (i = 2; i lte n; i=i+1) {
s_i = Mid(s,i-1,1);
for (j = 2; j lte m; j=j+1) {
t_j = Mid(t,j-1,1);
if (s_i is t_j) {
cost = 0;
}
else {
cost = 1;
}
d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1);
d[i][j] = min(d[i][j], d[i-1][j-1] + cost);
}
}
return d[n][m];
}
```

blog comments powered by Disqus
### Search CFLib.org

### Latest Additions

Kevin Cotton added

date2ExcelDate

May 5, 2016

Raymond Camden added

CapFirst

April 25, 2016

Chris Wigginton added

loremIpsum

January 18, 2016

Gary Stanton added

calculateArrival...

November 19, 2015

Sebastiaan Naafs - van Dijk added

getDaysInQuarter

November 13, 2015