COUNT = "_count"

def make_trie(words):

    """

    Args:

        words:

    """

    root = {}

    for word in words:

        current_dict = root

        for letter in word:

            current_dict = current_dict.setdefault(letter, {})

        if COUNT not in current_dict:

            current_dict[COUNT] = 1

        else:

            current_dict[COUNT] += 1

    return root

def longest_common_prefix(strs):

    """

    Args:

        strs:

    """

    def traverse_trie(dictionary, prefix):

        if len(prefix) > 100:

            return prefix

        if len(dictionary.keys()) == 1 and COUNT not in dictionary.keys():

            letter = list(dictionary.keys())[0]

            return traverse_trie(dictionary[letter], prefix + letter)

        else:

            return prefix

    trie = make_trie(strs)

    lcp_branches = []

    for branch in trie:

        branch_lcp = traverse_trie(trie[branch], branch)

        lcp_branches.append(branch_lcp)

    return lcp_branches