Longest common prefix: Difference between revisions

Longest common prefix (view source)

460 bytes removed , 9 years ago

→‎Python: Functional: revert to original version because the other version may have bad complexity; but use min & max instead of sort

Anonymous user

Revision as of 01:33, 21 March 2015 (view source) rosettacode>Spoon! (→‎{{header\|Python}}) ← Older edit		Revision as of 01:54, 21 March 2015 (view source) rosettacode>Spoon! (→‎Python: Functional: revert to original version because the other version may have bad complexity; but use min & max instead of sort) Newer edit →
Line 58: ===Python: Functional=== To see if all the n'th characters are the same I compare the min and max characters in the lambda function. We first observe that the longest common prefix of a set of strings must be the same as the longest common prefix of the lexicographically minimal and lexicographically maximal strings, since moving away lexicographically can only shorten the common prefix, never lengthen it. We <code>zip</code> the two strings, taking advantage of the fact that it stops at the end of the shortest sequence, to not need to worry about extra characters on the longer one. We compare each pair of characters and take them as long as they are equal. <lang python>from itertools import takewhile def lcp(s): return ''.join(ach[0] for ~~a,b~~ch in takewhile(lambda x: min(~~a,b~~x)~~: a~~ == bmax(x), zip(~~min(s), max(~~s)))) assert lcp("interspecies","interstelar","interstate") == "inters"