Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Radix sort solution in Speedy category for The End of Other by Renelvon
import collections
def radix_sort(strings_w_lengts, n):
'''All strings given must agree on the last (n - 1) positions.
Group them according to the n-th character (key).
Return True if there is a key which contains:
-- at least one string of length = depth
-- and another (larger) string
else recurse on each group (by key), one place towards the start.
Complexity: Each character of each string is checked at most once.
Note: This solution works comparably to a trie-based one.
'''
# Each key holds strings equal up tp the last n characters
ddict = collections.defaultdict(list)
# keys where a string of length exactly 'depth' was added
keys_to_check = set()
# Phase 1: Group them
for t in strings_w_lengts:
s, l = t
if l >= n: # drop smaller strings that are nobody's suffix
key = s[-n]
ddict[key].append(t)
if l == n:
keys_to_check.add(key)
# Phase 2: Check for solution
for k in keys_to_check:
if len(ddict[k]) > 1:
return True
# Phase 3: Recurse on all subproblems
for v in ddict.values():
if v and len(v) > 1 and radix_sort(v, n + 1):
return True
return False
prepare = lambda strings: ((s, len(s)) for s in strings)
checkio = lambda words_set: radix_sort(prepare(words_set), 1)
#These "asserts" using only for self-checking and not necessary for auto-testing
May 14, 2014
