Longest Common PrefixSolution

https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1162/

这道题brutal force的方法就不说了，是O(N)的复杂度。

关于search prefix的都可以用Trie来解决，复杂度是O(S) S是 String的长度

Trie Template:

https://app.gitbook.com/@pythongod/s/hackerland/trie-template

class TrieNode(object):
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie(object):
    def __init__(self):
        self.root = TrieNode()
    
    def addWord(self,word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.isWord = True
    
    def greatPrefix(self):
        node = self.root
        res = []
        while node:
            if node.isWord or len(node.children) > 1:
                return "".join(res)
            curr = list(node.children)[0]
            res.append(curr)
            node = node.children[curr]
        return "".join(res)
    
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ""
        trie = Trie()
        for s in strs:
            trie.addWord(s)
        return trie.greatPrefix()