思路：字典树

• 把所有字符串放到一颗字典树上

• 如果遇到了有多个孩子节点，或者遇到了终止符，就说明当前公共前缀已经到头了，返回的前缀就是最长公共前缀

  代码：

  ```python

  字典树

  class TrieNode: def init(self):

    self.isEnd: bool = False
    self.children: list = [None for _ in range(26)]

  def insert(self, words: list[str]) -> None:

    for word in words:
        curNode = self
        for ch in word:
            chNum = ord(ch) - ord('a')
            if curNode.children[chNum] == None:
                curNode.children[chNum] = TrieNode()
            curNode = curNode.children[chNum]
        curNode.isEnd = True
  

  def calculateChilden(self, curNode) -> int:

    countChilden = 0
    for i in range(26):
        if curNode.children[i] != None:
            countChilden += 1
  
    return countChilden
  

  def search(self, rootNode, word: str, commonPrefix: str) -> str:

    curNode = rootNode
    for ch in word:
        chNum = ord(ch) - ord('a')
  
        if self.calculateChilden(curNode) != 1:
            return commonPrefix
  
        if curNode.isEnd:
            return commonPrefix
  
        commonPrefix += ch
        curNode = curNode.children[chNum]
    return word
  

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str:

    node = TrieNode()
    node.insert(strs)
    return  node.search(node, strs[0], "")

```