Time Complexity:

The worst possible scenario is if all strings are the same and have a lot of characters. If N is the number of strings and M is the string with the most amount of characters, the worst case time complexity is O(N * M).

Space Complexity:

O(M) since we extend our dictionary only for one word.

class Trie:
    def __init__(self):
        self.root = {}

    def add_word(self, word): 
        curr = self.root
        for c in word:
            curr[c] = {}
            curr = curr[c]

    def check_prefix(self, word):
        curr = self.root
        prefix = ''
        count = 0
        for c in word:
            if c in curr:
                prefix += c
                count += 1
                curr = curr[c]
            else:
                break
        return prefix, count

    def show_trie(self):
        return self.root

class Solution:
    def longestCommonPrefix(self, strs):
        trie = Trie()
        trie.add_word(strs[0])
        final_prefix, final_count = '', float('inf')
        for word in strs:
            prefix, count = trie.check_prefix(word)
            if count < final_count:
                final_prefix, final_count = prefix, count
        # ToDo: Write Your Code Here.
        return final_prefix