Longest Common Prefix among all the given strings

Given a set of strings, write a program to find the longest common prefix (LCP) among all the strings. If there is no common prefix, return an empty string.

Input/Output Examples

plaintext
Example 1:
Input: ["flower", "flow", "flight"]
Output: "fl"
Explanation: The longest common prefix among all the strings is "fl".

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

Approach to Find the Longest Common Prefix using Trie

  1. Trie Data Structure:
    • A Trie (prefix tree) is a tree-like data structure used to efficiently store strings and perform operations like searching and prefix matching. Each node in the Trie represents a character of a string.
    • To solve the problem using a Trie:
      • First, insert all the strings into the Trie.
      • Then, traverse the Trie to find the longest path where all strings share the same prefix. The traversal stops when a node has more than one child or no more characters are left.
  2. Insertion into Trie:
    • Insert each string character by character into the Trie. Each character is a node in the Trie. If the character already exists in the current node, we move to the next node.
  3. Finding Longest Common Prefix:
    • After constructing the Trie, we find the longest common prefix by traversing from the root. We stop when:
      • A node has more than one child (meaning the strings diverge at this point).
      • A node corresponds to the end of a string.
  4. Edge Cases:
    • If the list of strings is empty, return an empty string.
    • If any string is empty, the common prefix is an empty string.

C++ Program for Longest Common Prefix using Trie

cpp
#include <iostream>
#include <vector>
using namespace std;

// Trie node structure
struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = NULL;
        }
        isEndOfWord = false;
    }
};

// Trie class
class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode();
    }

    // Insert a word into the Trie
    void insert(string word) {
        TrieNode* current = root;
        for (char ch : word) {
            int index = ch - 'a';
            if (current->children[index] == NULL) {
                current->children[index] = new TrieNode();
            }
            current = current->children[index];
        }
        current->isEndOfWord = true;
    }

    // Find the longest common prefix
    string longestCommonPrefix() {
        string prefix = "";
        TrieNode* current = root;

        while (true) {
            int count = 0;
            int index = -1;

            // Count how many children the current node has
            for (int i = 0; i < 26; i++) {
                if (current->children[i] != NULL) {
                    count++;
                    index = i;
                }
            }

            // If there's more than one child or the current node marks the end of a word, stop
            if (count != 1 || current->isEndOfWord) {
                break;
            }

            // Append the character to the prefix
            prefix += (char)(index + 'a');
            current = current->children[index];
        }

        return prefix;
    }
};

// Function to find the longest common prefix among a list of strings
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";

    Trie trie;

    // Insert all words into the Trie
    for (string word : strs) {
        trie.insert(word);
    }

    // Return the longest common prefix
    return trie.longestCommonPrefix();
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};
    cout << "Longest Common Prefix: " << longestCommonPrefix(strs) << endl;
    return 0;
}

Java Program for Longest Common Prefix using Trie

java
import java.util.*;

// Trie node class
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

// Trie class
class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // Find the longest common prefix
    public String longestCommonPrefix() {
        StringBuilder prefix = new StringBuilder();
        TrieNode current = root;

        while (true) {
            int count = 0;
            int index = -1;

            // Count how many children the current node has
            for (int i = 0; i < 26; i++) {
                if (current.children[i] != null) {
                    count++;
                    index = i;
                }
            }

            // If there's more than one child or the current node marks the end of a word, stop
            if (count != 1 || current.isEndOfWord) {
                break;
            }

            // Append the character to the prefix
            prefix.append((char) (index + 'a'));
            current = current.children[index];
        }

        return prefix.toString();
    }
}

// Function to find the longest common prefix among a list of strings
public class LongestCommonPrefixTrie {
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";

        Trie trie = new Trie();

        // Insert all words into the Trie
        for (String word : strs) {
            trie.insert(word);
        }

        // Return the longest common prefix
        return trie.longestCommonPrefix();
    }

    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println("Longest Common Prefix: " + longestCommonPrefix(strs));
    }
}

Python Program for Longest Common Prefix using Trie

python
# Trie node structure
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end_of_word = False

# Trie class
class Trie:
    def __init__(self):
        self.root = TrieNode()

    # Insert a word into the Trie
    def insert(self, word):
        current = self.root
        for ch in word:
            index = ord(ch) - ord('a')
            if current.children[index] is None:
                current.children[index] = TrieNode()
            current = current.children[index]
        current.is_end_of_word = True

    # Find the longest common prefix
    def longest_common_prefix(self):
        current = self.root
        prefix = []

        while True:
            count = 0
            index = -1

            # Count how many children the current node has
            for i in range(26):
                if current.children[i] is not None:
                    count += 1
                    index = i

            # If there's more than one child or the current node marks the end of a word, stop
            if count != 1 or current.is_end_of_word:
                break

            # Append the character to the prefix
            prefix.append(chr(index + ord('a')))
            current = current.children[index]

        return ''.join(prefix)

# Function to find the longest common prefix among a list of strings
def longest_common_prefix(strs):
    if not strs:
        return ""

    trie = Trie()

    # Insert all words into the Trie
    for word in strs:
        trie.insert(word)

    # Return the longest common prefix
    return trie.longest_common_prefix()

# Example usage
if __name__ == "__main__":
    strs = ["flower", "flow", "flight"]
    print("Longest Common Prefix:", longest_common_prefix(strs))
  • Time Complexity:
    • Insertion: O(N * M), where N is the number of strings and M is the average length of the strings.
    • Traversing the Trie to find the longest common prefix: O(M), where M is the length of the longest common prefix.
  • Space Complexity: O(N * M), where N is the number of strings and M is the average length of the strings, as we are storing the characters in the Trie.

DSA

2339

665

Related Articles