Space complexity using trie

compress-url-list.py

from pprint import pprint


class Node(dict):
    char = None

    def __init__(self, char):
        self.char = char

    def __str__(self):
        return '%s: %s' % (self.char, super(Node, self).__str__())


def add_data(root_node, data):
    parent_node = root_node
    for char in data:
        child_node = parent_node.get(char)
        if child_node is None:
            parent_node[char] = Node(char)
            parent_node = parent_node[char]
        else:
            parent_node = child_node


root_node = {}
data_list = ['donut.net', 'dog.com' , 'dog.org/about', 'dog.org/pug', 'dog.org']
for data in data_list:
    add_data(root_node, data)

pprint(root_node, indent=4)