0014. Longest Common Prefix

Easy | String + Trie | 16 ms (94.87%), 13.7 MB (39.95%)

❓ Problem Statement

Source: LeetCode - Longest Common Prefix GitHub: Solution / Performance

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 "".

✍🏻 Constraints & Example

Constraints:

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] consists of only lower-case English letters.

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

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

💡 Ideas

Instead of sorting the list of strings and find the answer between the longest string and shortest string, we could use the Trie data structure to find the answer. (Refer to 0208. Implement Trie)

We iterate through each word in the list to insert the characters plus the symbol of the end of word # into the Trie. Then, we traverse the Trie to get the longest common prefix.

• If the length of the hash table in a certain node does equal to 1 or the symbol of the end of the word exists, return the answer.

• Otherwise, we append the current char to the answer and move to the next node.

🤖 Python3

class Trie:
    def __init__(self):
        self.root = {}
        
    def insert(self, word):
        curNode = self.root
        
        for char in word:
            if char not in curNode: curNode[char] = {}
            curNode = curNode[char]
            
        curNode['#'] = True
        
    def longestCommonPrefix(self):
        prefix  = ''
        curNode = self.root
        
        while True:
            if len(curNode) == 1 and '#' not in curNode: 
                curChar = list(curNode.keys())[0]
                prefix += curChar
                curNode = curNode[curChar]
            else: 
                return prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # (base case)
        if not strs: return ''
        if len(strs) == 1: return strs[0]
        
        # ==================================================
        #  Trie                                            =
        # ==================================================
        # time  : O(n), n = number of all characters in the array
        # space : O(n) 

        trie = Trie()
        for word in strs: trie.insert(word)
            
        return trie.longestCommonPrefix()
    
        '''
        # ==================================================
        #  Array + Sort                                    =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        strs.sort()
        
        shortStr = strs[0]
        longStr  = strs[-1]
        prefix   = ''
        
        for i in range(len(shortStr)):
            if shortStr[i] != longStr[i]: return prefix
            else: prefix += shortStr[i]
                
        return prefix
        
        # ==================================================
        #  Python Built-in Functions                       =
        # ==================================================
        os.path.commonprefix(strs)     
        '''