unique_prefix.py

class Node(object):
    def __init__(self, depth):
        # Node children keyed by character
        self.children = {} 
        # Reference count
        self.count = 0
        # Depth from root node
        self.depth = depth
       
    def add(self, key):
        """ Move a word to a child node of this node and return """
        child = node.children.setdefault(key, Node(self.depth +1))
        child.count += 1
        self.count -= 1
        return child

    def unique(self):
        """ Is this node a shortest unique prefix?"""
        return self.count == 1 and len(self.children) == 0

if __name__ == "__main__":
    examples = ["dog", "cat", "dad", "cow", "weird", "cost-effective"]

    root = Node(0)
    nodes = [root]*len(examples)

    # Loop over character positions
    for i in range(max(map(len, examples))): 
        # Loop over input strings
        for j, ex in enumerate(examples):
            if not nodes[j].unique() and i < len(ex):
                char = ex[i]
                node = nodes[j]
                nodes[j] = node.add(char)

        if all([n.unique() for n in nodes]): break

    for node, ex in zip(nodes, examples):
        if not node.unique: print "WARNING: No unique prefix possible"
        print ex[:node.depth]