Problem Statement

Given a string array nums of length n. A string is called a complete string if every prefix of this string is also present in the array nums. Find the longest complete string in the array nums.

If there are multiple strings with the same length, return the lexicographically smallest one and if no string exists, return “None” (without quotes).

Examples

Example 1:

Input: nums = ["n", "ni", "nin", "ninj", "ninja", "nil"]
Output: ninja

Explanation: The word "ninja" is the longest word which has all its prefixes present in the array.

Example 2:

Input: nums = ["ninja", "night", "nil"]
Output: None

Explanation: There is no string that has all its prefix present in array. So we return None.

Example 3:

Input: nums = ["cat", "car", "cow", "c", "ca", "t", "r", "w"]
Output: cat

Different Approaches

1️⃣ Tries

Intuition:

By building a Trie from the array of words, checking prefixes becomes much easier. In a Trie, each node stands for a character, and the paths from the root to the nodes represent the prefixes found in the array. This setup quickly checks if a prefix exists by following the path in the Trie, making the process much faster and more efficient.

Approach:

1. Iterate through each word in the input list and insert it into the Trie.
2. Initialize an empty string to represent the longest complete string found so far.
3. Iterate through each word in the input list again and check if all its prefixes are present in the Trie.
4. If all prefixes are present: Compare the current word's length and lexicographical order with the current longest complete string.
5. Update the longest complete string if the current word is longer or comes earlier alphabetically.
6. If no complete string is found, return an empty string. Otherwise, return the longest complete string found.

Code:

#include <bits/stdc++.h>
using namespace std;

// Class representing each node of the Trie
class Node {
public:
    // To store references to child nodes
    Node* links[26];  
    // Flag to indicate end of a word
    bool flag = false;  

    // Checks if the current character link exists
    bool containsKey(char ch) {
        return (links[ch - 'a'] != NULL);
    }

    // Returns the next node corresponding to the character
    Node* get(char ch) {
        return links[ch - 'a'];
    }

    // Creates a link to the next node for the current character
    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

    // Marks the end of a word
    void setEnd() {
        flag = true;
    }

    // Checks if the current node is the end of a word
    bool isEnd() {
        return flag;
    }
};

// Class representing the Trie (Prefix Tree) structure
class Trie {
public:
    // Root node of the Trie
    Node* root;  

    // Initializes the Trie
    Trie() {
        root = new Node();
    }

    // Inserts a word into the Trie
    void insert(string word) {
        Node* node = root;
        for (int i = 0; i < word.size(); i++) {
            if (!node->containsKey(word[i])) {
                node->put(word[i], new Node());
            }
            node = node->get(word[i]);
        }
        // Marks the end of the inserted word
        node->setEnd();  
    }

    // Checks if all prefixes of the given word exist in the Trie
    bool checkIfAllPrefixExists(string word) {
        Node* node = root;
        for (int i = 0; i < word.size(); i++) {
            if (node->containsKey(word[i])) {
                node = node->get(word[i]);
                if (!node->isEnd()) {
                     // Prefix is incomplete, return false
                    return false; 
                }
            } else {
                // Return false if a character link is missing
                return false;  
            }
        }
        // All prefixes exist
        return true;  
    }
};

// Solution class to find the longest word with all its prefixes present
class Solution {
public:
    string completeString(vector<string>& nums) {
        // Create a new Trie
        Trie* obj = new Trie();  

        // Insert all words into the Trie
        for (int i = 0; i < nums.size(); i++) {
            obj->insert(nums[i]);
        }
         // Stores the longest valid word
        string longest = ""; 

        // Check each word to find the longest one where all prefixes exist
        for (int i = 0; i < nums.size(); i++) {
            if (obj->checkIfAllPrefixExists(nums[i])) {
                if (nums[i].size() > longest.size()) {
                    longest = nums[i];
                } else if (nums[i].size() == longest.size() && nums[i] < longest) {
                    // Lexicographically smaller word
                    longest = nums[i];  
                }
            }
        }
        // Return result or "None"

        return longest.empty() ? "None" : longest;  
    }
};

int main() {

    int t;
    cin >> t; 
    while (t--) {
        
        Solution sol;  

        string testCase;
	    cin >> testCase;
	    cout << testCase << endl; 
        
        int n;
        cin >> n; 
        vector<string> nums(n); 
        for (int i = 0; i < n; i++) {
            cin >> nums[i];  
        }

       
        string ans = sol.completeString(nums);
        cout << ans << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) * O(len), where len is the average length of all the strings.
• Space Complexity:O(N), where N is the total number of characters of all unique words.
  • Each node in the Trie contains an array of pointers to child nodes, typically 26 pointers for lowercase English letters.
  • The number of nodes created will be proportional to the number of characters in all unique words, resulting in a space complexity of O(N).