Python Solution Using Trie


  • 0
    M
    class TrieNode:
        
        def __init__(self):
            self.children = {}
            self.count = 0
            self.word = None
        
        def insert(self, word):
            node = self
            for ch in word:
                node.count += 1
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.word = word
        
        def longest_common_prefix(self, length):
            node = self
            s = ''
            while len(node.children) == 1:
                l = node.children.keys()[0]
                s += l
                node = node.children[l]
                if node.count != length:
                    break
            return s
        
    
    class Solution(object):
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            if not strs or not all(strs):
                return ""
            
            root = TrieNode()
            for s in strs:
                root.insert(s)
            
            length = len(strs)
            return root.longest_common_prefix(length)
            
            
    

  • 0
    M

    Brilliant!!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.