Check if the given Trie contains words starting from every alphabet

0 0 7 minutes read

Given a Trie, the task is to check if it contains words starting from every alphabet from [a – z]. Examples:

Input: keys[] = {“element”, “fog”, “great”, “hi”, “ok”, “ios”, “parrot”, “quiz”, “kim”, “mango”, “nature”, “apple”, “ball”, “cat”, “dog”, “lime”, “ruby”, “shine”, “tinkter”, “ultra”, “volly”, “wow”, “xerox”, “yak”, “zenon”, “joke”}
Output: Yes

Input: keys[] = {“zambiatek”, “for”, “zambiatek”}
Output: No

Approach: We just need to focus on the root node of the given Trie and no need to traverse other nodes. We simply check if Trie has all its child pointers pointing to valid nodes i.e. there are words starting from every character of the alphabet. Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
// Trie node
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
 
    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
};
 
// Returns new trie node (initialized to NULL)
struct TrieNode* getNode(void)
{
    struct TrieNode* pNode = new TrieNode;
 
    pNode->isEndOfWord = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}
 
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode* root, string key)
{
    struct TrieNode* pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // Mark last node as leaf
    pCrawl->isEndOfWord = true;
}
 
// Function to check if Trie contains words
// starting from all the alphabets
bool containsAll(TrieNode* root)
{
    // We check if root node has all childs
    // if None of them is NULL then we return true
    for (int i = 0; i < 26; i++) {
 
        // If there is no word in the trie starting
        // from the current alphabet
        if (root->children[i] == NULL)
            return false;
    }
    return true;
}
 
// Driver code
int main()
{
 
    string keys[] = { "element", "fog", "great", "hi", "ok",
                      "ios", "parrot", "quiz", "kim", "mango", "nature",
                      "apple", "ball", "cat", "dog", "lime", "ruby",
                      "shine", "tinkter", "ultra", "volly", "wow",
                      "xerox", "yak", "zenon", "joke" };
    int n = sizeof(keys) / sizeof(keys[0]);
 
    // Create the Trie
    struct TrieNode* root = getNode();
    for (int i = 0; i < n; i++)
        insert(root, keys[i]);
 
    // If trie contains words starting
    // from every alphabet
    if (containsAll(root))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

Python3

# Python implementation of the approach
 
# Alphabet size
ALPHABET_SIZE = 26
 
# Trie node
class TrieNode:
    def __init__(self):
        self.children = [None]*ALPHABET_SIZE
 
        # isEndOfWord is true if the node represents
        # end of a word
        self.isEndOfWord = False
 
# Returns new trie node (initialized to NULL)
def getNode():
    pNode = TrieNode()
 
    pNode.isEndOfWord = False
 
    for i in range(ALPHABET_SIZE):
        pNode.children[i] = None
 
    return pNode
 
# If not present, inserts key into trie
# If the key is prefix of trie node, just
# marks leaf node
def insert(root, key):
    pCrawl = root
 
    for i in range(len(key)):
        index = ord(key[i]) - ord('a')
        if not pCrawl.children[index]:
            pCrawl.children[index] = getNode()
 
        pCrawl = pCrawl.children[index]
 
    # Mark last node as leaf
    pCrawl.isEndOfWord = True
 
# Function to check if Trie contains words
# starting from all the alphabets
def containsAll(root):
    # We check if root node has all children
    # if None of them is None, then we return True
    for i in range(26):
        # If there is no word in the trie starting
        # from the current alphabet
        if not root.children[i]:
            return False
    return True
 
# Driver code
if __name__ == "__main__":
    keys = ["element", "fog", "great", "hi", "ok", "ios", "parrot",
            "quiz", "kim", "mango", "nature", "apple", "ball", "cat",
            "dog", "lime", "ruby", "shine", "tinkter", "ultra", "volly",
            "wow", "xerox", "yak", "zenon", "joke"]
    n = len(keys)
 
    # Create the Trie
    root = getNode()
    for i in range(n):
        insert(root, keys[i])
 
    # If trie contains words starting
    # from every alphabet
    if containsAll(root):
        print("Yes")
    else:
        print("No")
#This code is contributed by rudra1807raj

Java

// Java implementation of the approach
import java.util.Arrays;
 
// Trie node
class TrieNode {
  TrieNode[] children = new TrieNode[26];
  boolean isEndOfWord;
 
  TrieNode() {
    Arrays.fill(children, null);
    // isEndOfWord is true if the node represents
    // end of a word
    isEndOfWord = false;
  }
}
 
public class Trie {
  static final int ALPHABET_SIZE = 26;
 
  // Returns new trie node (initialized to NULL)
  static TrieNode getNode() {
    return new TrieNode();
  }
 
  // If not present, inserts key into trie
  // If the key is prefix of trie node, just
  // marks leaf node
  static void insert(TrieNode root, String key) {
    TrieNode pCrawl = root;
 
    for (int i = 0; i < key.length(); i++) {
      int index = key.charAt(i) - 'a';
      if (pCrawl.children[index] == null)
        pCrawl.children[index] = getNode();
      pCrawl = pCrawl.children[index];
    }
    // Mark last node as leaf
    pCrawl.isEndOfWord = true;
  }
 
  // Function to check if Trie contains words
  // starting from all the alphabets
  static boolean containsAll(TrieNode root) {
    // We check if root node has all childs
    // if None of them is NULL then we return true
    for (int i = 0; i < ALPHABET_SIZE; i++) {
      // If there is no word in the trie starting
      // from the current alphabet
      if (root.children[i] == null)
        return false;
    }
    return true;
  }
 
  // Driver code
  public static void main(String[] args) {
    String[] keys = { "element", "fog", "great", "hi", "ok", "ios", "parrot", "quiz", "kim", "mango", "nature",
                     "apple", "ball", "cat", "dog", "lime", "ruby", "shine", "tinkter", "ultra", "volly", "wow", "xerox",
                     "yak", "zenon", "joke" };
    int n = keys.length;
 
    // Create the Trie
    TrieNode root = getNode();
    for (int i = 0; i < n; i++)
      insert(root, keys[i]);
 
    // If trie contains words starting
    // from every alphabet
    if (containsAll(root))
      System.out.println("Yes");
    else
      System.out.println("No");
  }
}
 
// This code is contributed by Aman Kumar.

C#

// C# implementation of the approach
using System;
 
class TrieNode
{
public TrieNode[] children;
public bool isEndOfWord;
 
 
public TrieNode()
{
    children = new TrieNode[26];
    isEndOfWord = false;
}
}
 
class Trie
{
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
public void insert(TrieNode root, string key)
{
TrieNode pCrawl = root;
 
 
    for (int i = 0; i < key.Length; i++)
    {
        int index = key[i] - 'a';
        if (pCrawl.children[index] == null)
            pCrawl.children[index] = new TrieNode();
 
        pCrawl = pCrawl.children[index];
    }
 
    // Mark last node as leaf
    pCrawl.isEndOfWord = true;
}
 
// Function to check if Trie contains words
// starting from all the alphabets
public bool containsAll(TrieNode root)
{
    // We check if root node has all childs
    // if None of them is NULL then we return true
    for (int i = 0; i < 26; i++)
    {
        // If there is no word in the trie starting
        // from the current alphabet
        if (root.children[i] == null)
            return false;
    }
    return true;
}
}
 
class Program
{
// Driver code
static void Main(string[] args)
{
 
 
    string[] keys = { "element", "fog", "great", "hi", "ok",
                      "ios", "parrot", "quiz", "kim", "mango", "nature",
                      "apple", "ball", "cat", "dog", "lime", "ruby",
                      "shine", "tinkter", "ultra", "volly", "wow",
                      "xerox", "yak", "zenon", "joke" };
    int n = keys.Length;
 
    // Create the Trie
    Trie trie = new Trie();
    TrieNode root = new TrieNode();
    for (int i = 0; i < n; i++)
        trie.insert(root, keys[i]);
 
    // If trie contains words starting
    // from every alphabet
    if (trie.containsAll(root))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
}
}
//This code is contributed by rudra1807raj

Javascript

// Alphabet size
const ALPHABET_SIZE = 26;
 
// Trie node
class TrieNode {
constructor() {
this.children = Array(ALPHABET_SIZE).fill(null); // isEndOfWord is true if the node represents
// end of a word
this.isEndOfWord = false;
}
}
 
// Returns new trie node (initialized to NULL)
function getNode() {
const pNode = new TrieNode();
 
pNode.isEndOfWord = false;
 
for (let i = 0; i < ALPHABET_SIZE; i++) {
pNode.children[i] = null;
}
 
return pNode;
}
 
// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
function insert(root, key) {
let pCrawl = root;
 
for (let i = 0; i < key.length; i++) {
const index = key.charCodeAt(i) - "a".charCodeAt(0);
if (!pCrawl.children[index]) {
pCrawl.children[index] = getNode();
}pCrawl = pCrawl.children[index];
}
 
// Mark last node as leaf
pCrawl.isEndOfWord = true;
}
 
// Function to check if Trie contains words
// starting from all the alphabets
function containsAll(root) {
// We check if root node has all children
// if None of them is None, then we return True
for (let i = 0; i < 26; i++) {
// If there is no word in the trie starting
// from the current alphabet
if (!root.children[i]) {
return false;
}
}
return true;
}
 
// Driver code
const keys = [
"element",
"fog",
"great",
"hi",
"ok",
"ios",
"parrot",
"quiz",
"kim",
"mango",
"nature",
"apple",
"ball",
"cat",
"dog",
"lime",
"ruby",
"shine",
"tinkter",
"ultra",
"volly",
"wow",
"xerox",
"yak",
"zenon",
"joke",
];
const n = keys.length;
 
// Create the Trie
const root = getNode();
for (let i = 0; i < n; i++) {
insert(root, keys[i]);
}
 
// If trie contains words starting
// from every alphabet
if (containsAll(root)) {
console.log("Yes");
} else {
console.log("No");
}

Output:

Yes

Time Complexity: O(n*m) where n is the number of words in the input array and m is the maximum length of the words.
Auxiliary Space: O(ALPHABET_SIZE*m)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!