Longest Common Prefix

Patrick Leaton
Published: March 6, 2021, 10:52 p.m.
Problem Description

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:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

 

Description taken from https://leetcode.com/problems/longest-common-prefix/.

Problem Solution

#Individual Comparisons
#O(N) Time where N is the amount of characters in all strings, O(1) Space
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 0:
            return ""
        shortest_word = min(strs)
        for i in range(0, len(shortest_word)):
            for compare in strs:
                if compare[i] != shortest_word[i]:
                    return shortest_word[:i]
        return shortest_word
 
#Trie
#O(N) Time where N is the amount of characters in all strings, O(N) Space
class TrieNode:
    def __init__(self, val:str) -> None:
        self.val = val
        self.children = {}
 
class Trie:
    def __init__(self) -> None:
        self.root = TrieNode(None)
   
    def insert(self, word:str) -> None:
        curr_node = self.root
        for char in word:
            if char not in curr_node.children:
                curr_node.children[char] = TrieNode(char)
            curr_node = curr_node.children[char]
    
    def search(self, word:str) -> str:
        path = []
        curr_node = self.root
        for char in word:
            if len(curr_node.children) > 1:
                break
            path.append(char)
            curr_node = curr_node.children[char]
        return "".join(path)
       
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        trie = Trie()
        for word in strs:
            trie.insert(word)
        return trie.search(min(strs))

 

Problem Explanation

Compare Shortest Word Prefix

We can solve this problem by comparing each character in the shortest word to the same character in every other word.  Once we find a difference between characters, we will return the common prefix up to that difference.

This is sort of a Dynamic Programming approach.

First off, if we have an empty list of strings then the longest common prefix would be an empty string.

        if len(strs) == 0:
            return ""

 

If not, then we will grab the shortest string in the array.  This will stop us from getting an index out-of-bounds error when we do our traversals and worst-case scenario, this entire word is the longest common prefix so it is the best one to choose.

        shortest_word = min(strs)

 

Now let's iterate through each character in the shortest word.  

        for i in range(0, len(shortest_word)):

 

One character at a time, we will compare that character in the shortest word with the character at the same index within each other word.

If we find that the current character in the shortest word does not match a character at the same index within another word, we will return the substring only up to the current index, excluding the current index from the longest common prefix.

            for compare in strs:
                if compare[i] != shortest_word[i]:
                    return shortest_word[:i]

 

If we didn't find a difference then the entire shortest word is the longest common prefix.

        return shortest_word

Trie Prefix Tree

Even though this is an easy-level question, and the previous solution was so much more concise, if we're given a problem that involves traversing common prefixes between multiple strings, a Prefix Tree, Trie, is a fantastic approach.

The benefit of a Trie is that common prefixes share the same branch.  If we push all of the characters from each word into the Trie, then that means all we need to do is return the common branch among all of the word branches.

If we take the first example, after inserting all of the words into our Trie, we would have something like this:

                    f
                    |
                    l
                /      \
             o           i
            /               \
          w                 g
        /                      \
      e                         h
    /                              \
  r                                 t
 
As we can see, before we get to diverging paths, everything up to that point will be a common prefix.

Let's start by creating our Trie node class.

Each Trie node will have for attributes a character value and a HashMap of child character values.

class TrieNode:
    def __init__(self, val:str) -> None:
        self.val = val
        self.children = {}

Next, we'll make our Trie class.

We'll instantiate a null root value once this class is run.

class Trie:
    def __init__(self) -> None:
        self.root = TrieNode(None)

We'll create an insert function for creating Trie nodes for each character in each word.

    def insert(self, word:str) -> None:

 

Let's create a current node pointer and set it at the root.

        curr_node = self.root

 

Then, for each character in the current input word, if the current character isn't already in the current node's children, we will instantiate a new node for the current character and create its mapping to the current character within the current node's children.

        for char in word:
            if char not in curr_node.children:
                curr_node.children[char] = TrieNode(char)

 

After we have finished with that, or if we didn't have to because it was already shared as a common prefix, we will move our current node pointer down the current branch to the node of the current character.

            curr_node = curr_node.children[char]

Now we will make our search function which we will use to collect the characters of the common prefix branch.

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

 

Let's initialize a list that we'll place characters within the common path into and a current node pointer set at the root.

        path = []
        curr_node = self.root

 

For each character in the current word, we will continue moving our pointer down the character's respective Trie node.

        for char in word:

 

If we ever get to a point where we find a divergent path, then we will break because we no longer have a common prefix.

            if len(curr_node.children) > 1:
                break

 

Otherwise, we will append the current character to our path and continue moving our pointer down to its child character node from the input word.

            path.append(char)
            curr_node = curr_node.children[char]

 

Once we have completed traversing the input word's characters, meaning that the entire word was a common prefix, or we broke from our loop because we found a divergent path, we will join the characters in the path to join a string then return that string.

        return "".join(path)

Now that we have made our Trie node class, our Trie class, and all of the helper functions we need, we will now instantiate our Trie, insert all of the characters from each word into it and return the longest common prefix by searching the minimum length word of the Trie.

        trie = Trie()
        for word in strs:
            trie.insert(word)
        return trie.search(min(strs))