Longest Common Prefix using Trie | DSA in C++ - Software Development PDF Download

Introduction

In computer science, the "Longest Common Prefix" (LCP) problem refers to finding the longest common prefix among a set of strings. One efficient way to solve this problem is by using a data structure called a Trie. This article will introduce you to the concept of Tries and demonstrate how to find the longest common prefix using a Trie data structure in C++.

What is a Trie?

A Trie, also known as a prefix tree, is a tree-like data structure commonly used for efficient string search operations. It provides a fast way to store and retrieve strings by organizing them based on their prefixes. Each node in a Trie represents a character, and the edges represent the possible characters that can follow that node.

Implementing a Trie in C++

To implement a Trie in C++, we can define a TrieNode structure that contains an array or a map of child nodes, representing the characters. Here's an example of the TrieNode structure:

struct TrieNode {

    TrieNode* children[26];  // Assuming lowercase English alphabets

    bool isEndOfWord;

};

Finding the Longest Common Prefix using a Trie

To find the longest common prefix among a set of strings using a Trie, we need to insert all the strings into the Trie and then traverse it until we find a node with more than one child or reach the end of any string. The characters encountered during traversal will form the longest common prefix.

Code Examples and Explanation

Trie Implementation

Let's begin by implementing a Trie data structure in C++. Here's the code:

class Trie {

private:

    TrieNode* root;

public:

    Trie() {

        root = new TrieNode();

    }

    void insert(const string& word) {

        TrieNode* curr = root;

        for (char ch : word) {

            int index = ch - 'a';

            if (!curr->children[index])

                curr->children[index] = new TrieNode();

            curr = curr->children[index];

        }

        curr->isEndOfWord = true;

    }

    // Additional Trie operations can be added here (e.g., search, delete)

};

Finding the Longest Common Prefix

Using the Trie structure, we can now find the longest common prefix among a set of strings. Here's the code:

string findLongestCommonPrefix(vector<string>& strs) {

    Trie trie;

    for (const string& word : strs)

        trie.insert(word);

    string prefix;

    TrieNode* curr = trie.root;

    while (curr && !curr->isEndOfWord && countChildren(curr) == 1) {

        for (int i = 0; i < 26; i++) {

            if (curr->children[i]) {

                prefix.push_back('a' + i);

                curr = curr->children[i];

                break;

            }

        }

    }

    return prefix;

}

int countChildren(TrieNode* node) {

    int count = 0;

    for (int i = 0; i < 26; i++) {

        if (node->children[i])

            count++;

    }

    return count;

}

Explanation:

• The 'findLongestCommonPrefix' function takes a vector of strings 'strs' as input and creates a Trie by inserting all the strings into it using the 'insert' function.
• It initializes an empty string 'prefix' and starts traversing the Trie from the root node.
• It continues traversing as long as the current node is not null, not the end of any word, and has only one child.
• During each traversal, it finds the first non-null child node and appends the corresponding character to the 'prefix' string.
• Finally, it returns the longest common prefix found.

Sample Problems and Solutions

Problem 1: Find the longest common prefix among a set of strings.

• Input: {"flower", "flow", "flight"}
• Output: "fl"

By using the Trie implementation and the 'findLongestCommonPrefix' function, we can obtain the correct output "fl" for the given input.

Problem 2: Find the longest common prefix among a set of strings.

• Input: {"dog", "racecar", "car"}
• Output: ""

Again, using the Trie implementation and the 'findLongestCommonPrefix' function, we can obtain the correct output "" (empty string) for the given input.

Conclusion

In this article, we explored the concept of Tries and learned how to find the longest common prefix among a set of strings using a Trie data structure in C++. We implemented a Trie, explained the algorithm to find the longest common prefix, and provided code examples along with sample problems and solutions. Tries are powerful data structures for efficient string operations, and understanding them can be beneficial in various programming scenarios.