Longest Common Prefix — LC Easy (Medium)

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False
class Solution:
    def __init__(self):
        self.root = TrieNode()
        
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for word in strs:
            if word == "":
                return ""
            self.insert(word)
            
        cur = self.root.children
        
        strReturn = []
        
        while len(cur) == 1:
            
            strAdd = [*cur.keys()]
            strReturn.append(strAdd[0])
            if cur[strAdd[0]].endOfWord:
                break
            cur = cur[strAdd[0]].children
            
        return ''.join(strReturn)
            
    def insert(self, word: str) -> None:
        cur = self.root
        
        for char in word:
            if char not in cur.children:
                cur.children[char] = TrieNode()
            cur = cur.children[char]
            
        cur.endOfWord = True