import collections
class TrieNode(object):
    def __init__(self, letter=None):
        self.letter = letter
        self.freq = 1
        self.suffixes = collections.OrderedDict()

    def add(self, word):
        node = self
        for letter in word:
            if not letter in node.suffixes:
                node.suffixes[letter] = TrieNode(letter)
            else:
                node.suffixes[letter].freq += 1
            node = node.suffixes[letter]

    def __str__(self):
        s = str(self.letter) + ':' + str(self.freq) + '{'
        for v in self.suffixes.values():
            s += str(v)
        s += '}'
        return s

class Solution:
    # @param A : list of strings
    # @return a list of strings
    def prefix(self, A):
        trie = TrieNode()
        for word in A:
            trie.add(word)
        print(trie)
        res = []
        def dfs(node, path=None):
            if not path:
                path = []
            if node:
                if node.letter and len(node.suffixes) < 2 and node.freq == 1:
                    res.append(''.join(path[1:]+[node.letter]))
                else:
                    for suffix in node.suffixes:
                        dfs(node.suffixes[suffix], path+[node.letter])
        dfs(trie)
        return res

if __name__ == '__main__':
    s = Solution()
    print(s.prefix(['abde', 'abc', 'bc']))
    print(s.prefix(['zebra', 'dog', 'duck', 'dove']))
    print(s.prefix([ "bearcat", "bert" ]))