Levenshtein distance

Function Lev(s As String, t As String) As Variant

Dim i As Integer ' iterates through s

Dim j As Integer ' iterates through t

Dim s_i As String ' ith character of s

Dim t_j As String ' jth character of t

Dim cost As Integer ' cost

' Step 1

Dim n As Integer

n = Len(s)

'length of s

Dim m As Integer

m = Len(t)

'length of t

If n = 0 Then

Lev = m

End If

If m = 0 Then

Lev = n

End If

Dim d(0 To 10, 0 To 10) As Integer

' Step 2

For i = 0 To n

d(i, 0) = i

Next i

For j = 0 To m

d(0, j) = j

Next j

' Step 3

For i = 1 To n

s_i = Mid(s, i, 1)

' Step 4

For j = 1 To m

t_j = Mid(t, j, 1)

' Step 5

If s_i = t_j Then

cost = 0

Else

cost = 1

End If

' Step 6

d(i, j) = Application.WorksheetFunction.Min(Application.WorksheetFunction.Min((d((i - 1), j) + 1), (d(i, (j - 1)) + 1)), (d((i - 1), (j - 1)) + cost))

Next j

Next i

' Step 7

Lev = d(n, m) / Application.WorksheetFunction.Max(m, n)

End Function