1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
' Challenge 096
'
' TASK #2 › Edit Distance
' Submitted by: Mohammad S Anwar
' You are given two strings $S1 and $S2.
'
' Write a script to find out the minimum operations required to convert $S1
' into $S2. The operations can be insert, remove or replace a character. Please
' check out Wikipedia page for more information.
'
' Example 1:
' Input: $S1 = "kitten"; $S2 = "sitting"
' Output: 3
'
' Operation 1: replace 'k' with 's'
' Operation 2: replace 'e' with 'i'
' Operation 3: insert 'g' at the end
' Example 2:
' Input: $S1 = "sunday"; $S2 = "monday"
' Output: 2
'
' Operation 1: replace 's' with 'm'
' Operation 2: replace 'u' with 'o'
function min(a as integer, b as integer) as integer
if a < b then
min = a
else
min = b
end if
end function
function min3(a as integer, b as integer, c as integer) as integer
min3 = min(a, min(b, c))
end function
function wag_fish_dist(a as string, b as string) as integer
dim i as integer, j as integer, subst_cost as integer
' define a table where d(i,j) is the Levenshtein distance between
' first i chars of a and first j chars of b
dim d(len(a)+1, len(b)+1) as integer
' source prefixes can be transformed into empty string by dropping chars
for i = 1 to len(a)
d(i,0) = i
next i
' target prefixes can be reached from empty source prefix by inserting chars
for j = 1 to len(b)
d(0,j) = j
next j
' flood-fill the rest of the table
for j = 1 to len(b)
for i = 1 to len(a)
if mid(a,i,1) = mid(b,j,1) then
subst_cost = 0
else
subst_cost = 1
end if
d(i,j) = min3(d(i-1,j)+1, _ ' deletion
d(i,j-1)+1, _ ' insertion
d(i-1,j-1)+subst_cost) ' substitution
next i
next j
' distance is in lower bottom cell
wag_fish_dist = d(len(a), len(b))
end function
print wag_fish_dist(command(1), command(2))
|
