facebook_find_valid_letter_sequence_graph_dfs.py

class Vertex:
    def __init__(self, value):
        self.value = value
        self.edges = []

class NewLanguage:
    def find_valid_sequence(self, words):
        self.word_map = {}

        #build alphabet graph
        for word in words:
            prev = None
            for c in word:
                if c not in self.word_map:
                    self.word_map[c] = Vertex(c)
                
                v = self.word_map[c]

                if prev != None:
                    prev.edges.append(v)
                prev = v

        # do dfs to find one valid sequence. end after first iteration.
        start = None
        for k in self.word_map:
            start = self.word_map[k]
            break
        
        result = [start.value]
        current = start
        while(len(current.edges)> 0):
            current = current.edges[0]
            result.append(current.value)
        
        return "".join(result)

n = NewLanguage()
input = ["abcdefo", "begz", "hijk", "abcedefgh", "ikom"]
print("input = {}, output = {}".format(input, n.find_valid_sequence(input)))