def calc_cache_pos(strings, indexes): factor = 1 pos = 0 for s, i in zip(strings, indexes): pos += i * factor factor *= len(s) return pos def lcs_back(strings, indexes, cache): if -1 in indexes: return "" match = all(strings[0][indexes[0]] == s[i] for s, i in zip(strings, indexes)) if match: new_indexes = [i - 1 for i in indexes] result = lcs_back(strings, new_indexes, cache) + strings[0][indexes[0]] else: substrings = [""] * len(strings) for n in range(len(strings)): if indexes[n] > 0: new_indexes = indexes[:] new_indexes[n] -= 1 cache_pos = calc_cache_pos(strings, new_indexes) if cache[cache_pos] is None: substrings[n] = lcs_back(strings, new_indexes, cache) else: substrings[n] = cache[cache_pos] result = max(substrings, key=len) cache[calc_cache_pos(strings, indexes)] = result return result def lcs(strings): """ >>> lcs(['666222054263314443712', '5432127413542377777', '6664664565464057425']) '54442' >>> lcs(['abacbdab', 'bdcaba', 'cbacaa']) 'baa' """ if len(strings) == 0: return "" elif len(strings) == 1: return strings[0] else: cache_size = 1 for s in strings: cache_size *= len(s) cache = [None] * cache_size indexes = [len(s) - 1 for s in strings] return lcs_back(strings, indexes, cache)