class TreeNode:
    def __init__(self, val):
        self.val = val
        self.counter = 1
        self.children = []

class Solution:
    # @param A : list of strings
    # @return a list of strings
    def prefix(self, A):
        head = TreeNode('')
        head.counter = 0

        for s in A:
            n = head
            for i in range(len(s)):
                found = False
                for child in n.children:
                    if child.val == s[:i+1]:
                        found = True
                        n = child
                        n.counter += 1
                        break
                if not found:
                    newChild = TreeNode(s[:i+1])
                    n.children.append(newChild)
                    n = newChild


        result = []

        for s in A:
            n = head
            i = 0
            found = False
            while i < len(s) and not found:
                for child in n.children:
                    if child.val == s[:i+1]:
                        n = child
                        if n.counter == 1:
                            result.append(s[:i+1])
                            found = True
                i += 1

        return result