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: YesInput: keys[] = {“neveropen”, “for”, “neveropen”}
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 nodestruct 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 nodevoid 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 alphabetsbool 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 codeint 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 sizeALPHABET_SIZE = 26# Trie nodeclass 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 nodedef 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 alphabetsdef 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 codeif __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 approachimport java.util.Arrays;// Trie nodeclass 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 approachusing 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 nodepublic 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 alphabetspublic 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 codestatic 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 sizeconst ALPHABET_SIZE = 26;// Trie nodeclass TrieNode {constructor() {this.children = Array(ALPHABET_SIZE).fill(null); // isEndOfWord is true if the node represents// end of a wordthis.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 nodefunction 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 leafpCrawl.isEndOfWord = true;}// Function to check if Trie contains words// starting from all the alphabetsfunction containsAll(root) {// We check if root node has all children// if None of them is None, then we return Truefor (let i = 0; i < 26; i++) {// If there is no word in the trie starting// from the current alphabetif (!root.children[i]) {return false;}}return true;}// Driver codeconst 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 Trieconst root = getNode();for (let i = 0; i < n; i++) {insert(root, keys[i]);}// If trie contains words starting// from every alphabetif (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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
