There is a secret string which is unknown to you. Given a collection of random triplets from the string, recover the original string. 

A triplet here is defined as a sequence of three letters such that each letter occurs somewhere before the next in the given string. "whi" is a triplet for the string "whatisup".

As a simplification, you may assume that no letter occurs more than once in the secret string.

You can assume nothing about the triplets given to you other than that they are valid triplets and that they contain sufficient information to deduce the original string. In particular, this means that the secret string will never contain letters that do not occur in one of the triplets given to you.

Difficulty: MEDIUM

Starter code:
def recoverSecret(triplets):
	

Solutions:
def recoverSecret(triplets):
	r = list(set([i for l in triplets for i in l]))
	for l in triplets:
		fix(r, l[1], l[2])
		fix(r, l[0], l[1])
	return ''.join(r)

def fix(l, a, b):
	if l.index(a) > l.index(b):
		l.remove(a)
		l.insert(l.index(b), a)


def recoverSecret(triplets):
	letters = list(set([l for t in triplets for l in t]))
	for t in triplets * len(letters):
		for i in range(len(t) - 1):
			(a, b) = (letters.index(t[i]), letters.index(t[i + 1]))
			if a > b:
				(letters[b], letters[a]) = (letters[a], letters[b])
	return ''.join(letters)


import collections, functools, itertools

def recoverSecret(triplets):
	graph = Graph()
	for triplet in triplets:
		for (i, j) in pairwise(triplet):
			graph[i].goes_to(graph[j])
	cardinality = lambda node: len([p for p in node.parents if p.value in graph])
	getnext = functools.partial(min, graph.viewvalues(), key=cardinality)
	word = (graph.pop(getnext().value).value for i in xrange(len(graph)))
	return ''.join(word)

class Graph(collections.defaultdict):

	def __missing__(self, key):
		self[key] = Node(key)
		return self[key]

class Node(object):

	def __init__(self, value):
		self.value = value
		self.parents = []

	def goes_to(self, child):
		child.parents.append(self)

def pairwise(iterable):
	(a, b) = itertools.tee(iterable)
	next(b, None)
	return itertools.izip(a, b)


def recoverSecret(a):
	out = list(zip(*a))
	h = [j for j in set(out[0]) - set(out[1] + out[2])]
	for i in a:
		if i[0] in h:
			(i[:2], i[2]) = (i[1:], '')
	return h[0] + recoverSecret(a) if h else str()


def recoverSecret(triplets):
	res = ''
	while triplets != []:
		non_firsts = [num for t in triplets for num in t[1:]]
		firsts = [t[0] for t in triplets]
		for f in firsts:
			if f not in non_firsts:
				res += f
				for t in triplets:
					if t[0] == f:
						t.pop(0)
				break
		triplets = [t for t in triplets if t != []]
	return res


def recoverSecret(triplets):
	ansList = list({triplet[i] for i in range(3) for triplet in triplets})
	indexDict = {letter: i for (i, letter) in enumerate(ansList)}
	isModified = True
	while isModified:
		isModified = False
		for triplet in triplets:
			for i in range(2):
				if indexDict[triplet[i]] > indexDict[triplet[i + 1]]:
					isModified = True
					(indexDict[triplet[i]], indexDict[triplet[i + 1]]) = (indexDict[triplet[i + 1]], indexDict[triplet[i]])
	for k in indexDict.keys():
		ansList[indexDict[k]] = k
	return ''.join(ansList)


from itertools import cycle

def recoverSecret(ts):
	orders = set(sum([[(a, b), (b, c), (a, c)] for (a, b, c) in ts], []))
	(secret, complete) = (list(set((l for t in ts for l in t))), False)
	for (a, b) in cycle(orders):
		(i, j) = (secret.index(a), secret.index(b))
		complete = i < j and complete + 1
		if j < i:
			(secret[j], secret[i]) = (a, b)
		elif complete >= len(orders):
			break
	return ''.join(secret)


from collections import defaultdict

def recoverSecret(triplets):
	letters = defaultdict(set)
	for (a, b, c) in triplets:
		letters[a].add(b)
		letters[a].add(c)
		letters[b].add(c)
	for (key, value) in list(letters.items()):
		for after_key in value:
			letters[key] = letters[key].union(letters[after_key])
	return ''.join((k for (k, _) in sorted(iter(letters.items()), key=lambda __v: len(__v[1]), reverse=True)))


def recoverSecret(triplets):
	res = ''
	table = {}
	visited = set()
	for (a, b, c) in triplets:
		if not table.has_key(a):
			table[a] = set()
		if not table.has_key(b):
			table[b] = set()
		if not table.has_key(c):
			table[c] = set()
		table[a].add(b)
		table[a].add(c)
		table[b].add(c)
	count = len(table.keys())
	while len(visited) < count:
		Min = count
		c = ''
		for (k, v) in table.iteritems():
			l = len([elem for elem in v if elem not in visited])
			if l < Min and k not in visited:
				Min = l
				c = k
		visited.add(c)
		res += c
	return res[::-1]


def recoverSecret(triplets):
	answer = list(set([item for sublist in triplets for item in sublist]))
	clues = []
	for t in triplets:
		clues.append([t[0], t[1]])
		clues.append([t[1], t[2]])
	while True:
		changed = False
		for pair in clues:
			left = answer.index(pair[0])
			right = answer.index(pair[1])
			if left > right:
				(answer[left], answer[right]) = (answer[right], answer[left])
				changed = True
		if not changed:
			break
	return ''.join(answer)