blob: 66cafdbf04c06e95c26802f3fd56d26acffc4d55 (
plain)
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
|
#!/usr/bin/env python
# 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'
import sys
def wag_fis_dist(a, b):
# define a table where d[i,j] is the Levenshtein distance between
# first i chars of a and first j chars of b
d = [ [ 0 for j in range(0, len(b)+1) ] for i in range(0, len(a)+1) ]
# source prefixes can be transformed into empty string by dropping chars
for i in range(1, len(a)+1):
d[i][0] = i
# target prefixes can be reached from empty source prefix by inserting chars
for j in range(1, len(b)+1):
d[0][j] = j
# flood-fill the rest of the table
for j in range(1, len(b)+1):
for i in range(1, len(a)+1):
subst_cost = 0 if a[i-1] == b[j-1] else 1
d[i][j] = min(d[i-1][j]+1, # deletion
d[i][j-1]+1, # insertion
d[i-1][j-1]+subst_cost) # substitution
# distance is in lower bottom cell
return d[len(a)][len(b)]
a, b = tuple(sys.argv[1:3])
print(wag_fis_dist(a, b))
|
