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
|
#!/usr/bin/env python3
###########################################################################
# script name: ch-2.py #
# #
# https://github.com/user-person #
# #
# https://perlweeklychallenge.org/blog/perl-weekly-challenge-057/ #
# #
# Shortest Unique Prefix #
# Write a script to find the shortest unique prefix for each each word #
# in the given list. The prefixes will not necessarily be of the same #
# length. #
# #
# Sample Input #
# [ "alphabet", "book", "carpet", "cadmium", "cadeau", "alpine" ] #
# Expected Output #
# [ "alph", "b", "car", "cadm", "cade", "alpi" ] #
# #
###########################################################################
def charsMatch(string1, string2):
count = 0
limit = 0
s1 = list(string1)
s2 = list(string2)
if len(s2) > len(s1):
limit = len(s1)
else:
limit = len(s2)
for i in range(limit-1):
if s1[i] == s2[i]:
count += 1
else:
break
if count + 1 < limit:
count += 1
return count
unSorted = ['alphabet', 'book', 'carpet', 'cadmium', 'cadeau', 'alpine']
prefix = {}
sortedList = sorted(unSorted)
diff = 0
for i in range(len(sortedList)):
if i == 0:
diff = charsMatch( sortedList[i], sortedList[i+1] )
elif i == len(sortedList)-1:
diff = charsMatch( sortedList[ len(sortedList)-2 ], sortedList[ len(sortedList)-1 ] )
else:
before = charsMatch( sortedList[i-1], sortedList[i] )
after = charsMatch( sortedList[i], sortedList[i+1] )
if before > after:
diff = before
else:
diff = after
prefix[ sortedList[i] ] = sortedList[i][:diff]
print('[ ',end='')
for j in range(len(unSorted)):
if j > 0:
print(', ', end='')
print('"' + prefix[ unSorted[j] ] + '"', end='')
print(']')
# output:
#
# [ "alph", "b", "car", "cadm", "cade", "alpi"]
|
