Given an array of strings arr[] and Q queries where each query consists of a string str, the task is to find the longest string in the array that matches with prefix of the given string str i.e. the string must be prefix of str.
Examples:
Input: arr[] = {“GeeksForGeeks”, “GeeksForGeeksd”, “Arnab”, “Art”}, q[] = {“GeeksForGeeks”, “Ar”, “Art”}
Output: GeeksForGeeks -1 Art
Input: arr[] = {“Geek”, “Geek”, “Geekss”, “Geekk”}, q[] = {“Geek”, “Geeks”, “Geekk”, “Gee”}
Output: Geek -1 Geekk -1
Naive approach: For every given string traverse through the array and check for the string which matches with prefix of the given string and store and print the longest string. Efficient Approach: This problem can be solved using a Trie. We will form an trie and insert the strings of the array in the trie and find the longest string that completely matches with the prefix of the given string. 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 NULLs)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(); if (i == key.length() - 1) // Mark last node as leaf pCrawl->children[index]->isEndOfWord = true; pCrawl = pCrawl->children[index]; }}string getString(char x){ // string class has a constructor // that allows us to specify size of // string as first parameter and character // to be filled in given size as second // parameter. string s(1, x); return s;}// Function to return the// longest required stringstring search(struct TrieNode* root, string key){ struct TrieNode* pCrawl = root; // Prefix of the string string s = ""; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->children[index]) break; s += getString((char)key[i]); pCrawl = pCrawl->children[index]; } if (pCrawl->isEndOfWord) return s; return "-1";}// Driver codeint main(){ string arr[] = { "Geeks", "Geek", "Geekss", "Geekks" }; int n = sizeof(arr) / sizeof(string); // Construct trie struct TrieNode* root = getNode(); for (int i = 0; i < n; i++) insert(root, arr[i]); string queries[] = { "Geek", "Geeks", "Geekk", "Gee" }; int q = sizeof(queries) / sizeof(string); for (int i = 0; i < q; i++) cout << search(root, queries[i]) << endl; return 0;} |
Java
import java.util.ArrayList;// Trie nodeclass TrieNode { TrieNode[] children = new TrieNode[26]; // isEndOfWord is true if the node represents // end of a word boolean isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) children[i] = null; }}public class Trie { TrieNode root; Trie() { root = new TrieNode(); } // If not present, inserts key into trie // If the key is prefix of trie node, just // marks leaf node void insert(String key) { int n = key.length(); TrieNode pCrawl = root; for (int i = 0; i < n; i++) { int index = key.charAt(i) - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = new TrieNode(); pCrawl = pCrawl.children[index]; } //Making True because we have reached to end pCrawl.isEndOfWord = true; } // Function to return the // longest required string String search(String key) { int n = key.length(); TrieNode pCrawl = root; StringBuilder s = new StringBuilder(); for (int i = 0; i < n; i++) { int index = key.charAt(i) - 'a'; if (pCrawl.children[index] == null) break; s.append(key.charAt(i)); pCrawl = pCrawl.children[index]; } if (pCrawl != null && pCrawl.isEndOfWord) return s.toString(); return "-1"; } public static void main(String[] args) { Trie trie = new Trie(); String[] arr = { "neveropen", "geek", "neveropens", "geekks" }; int n = arr.length; // Inserting every string into trie for (int i = 0; i < n; i++) trie.insert(arr[i]); String[] queries = { "geek", "neveropen", "geekk", "gee" }; int q = queries.length; for (int i = 0; i < q; i++) System.out.println(trie.search(queries[i])); }} |
Python3
# Python implementation of the approach# Trie nodeclass TrieNode: def __init__(self): self.children = [None] * 26 # isEndOfWord is true if the node represents # end of a word self.is_end_of_word = False# Returns new trie node (initialized to None)def get_node(): node = TrieNode() return node# If not present, inserts key into trie# If the key is prefix of trie node, just# marks leaf nodedef insert(root, key): crawl = root for i in range(len(key)): index = ord(key[i]) - ord('a') if not crawl.children[index]: crawl.children[index] = get_node() if i == len(key) - 1: crawl.children[index].is_end_of_word = True crawl = crawl.children[index]# Function to return the# longest required stringdef search(root, key): crawl = root # Prefix of the string s = "" for i in range(len(key)): index = ord(key[i]) - ord('a') if not crawl.children[index]: break s += key[i] crawl = crawl.children[index] if crawl and crawl.is_end_of_word: return s return "-1"# Driver codedef main(): arr = ["Geeks", "Geek", "Geekss", "Geekks"] n = len(arr) # Construct trie root = get_node() for i in range(n): insert(root, arr[i]) queries = ["Geek", "Geeks", "Geekk", "Gee"] q = len(queries) for i in range(q): print(search(root, queries[i]))if __name__ == "__main__": main()# This code is contributed by Aman Kumar. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;// Trie nodeclass TrieNode { public TrieNode[] children = new TrieNode[26]; // isEndOfWord is true if the node represents // end of a word public bool isEndOfWord; public TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) children[i] = null; }}public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // If not present, inserts key into trie // If the key is prefix of trie node, just // marks leaf node public void Insert(string key) { int n = key.Length; TrieNode pCrawl = root; for (int i = 0; i < n; i++) { int index = key[i] - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = new TrieNode(); pCrawl = pCrawl.children[index]; } //Making True because we have reached to end pCrawl.isEndOfWord = true; } // Function to return the // longest required string public string Search(string key) { int n = key.Length; TrieNode pCrawl = root; System.Text.StringBuilder s = new System.Text.StringBuilder(); for (int i = 0; i < n; i++) { int index = key[i] - 'a'; if (pCrawl.children[index] == null) break; s.Append(key[i]); pCrawl = pCrawl.children[index]; } if (pCrawl != null && pCrawl.isEndOfWord) return s.ToString(); return "-1"; } public static void Main(string[] args) { Trie trie = new Trie(); string[] arr = { "neveropen", "geek", "neveropens", "geekks" }; int n = arr.Length; // Inserting every string into trie for (int i = 0; i < n; i++) trie.Insert(arr[i]); string[] queries = { "geek", "neveropen", "geekk", "gee" }; int q = queries.Length; for (int i = 0; i < q; i++) Console.WriteLine(trie.Search(queries[i])); }}// this code is contributed by bhardwajji |
Javascript
// Trie nodeclass TrieNode {constructor() {this.children = Array(26).fill(null);// isEndOfWord is true if the node represents end of a wordthis.is_end_of_word = false;}}// Returns new trie node (initialized to null)function get_node() {const node = new TrieNode();return node;}// If not present, inserts key into trie// If the key is prefix of trie node, just marks leaf nodefunction insert(root, key) {let crawl = root;for (let i = 0; i < key.length; i++) {const index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);if (!crawl.children[index]) {crawl.children[index] = get_node();}if (i === key.length - 1) {crawl.children[index].is_end_of_word = true;}crawl = crawl.children[index];}}// Function to return the longest required stringfunction search(root, key) {let crawl = root;// Prefix of the stringlet s = "";for (let i = 0; i < key.length; i++) {const index = key[i].charCodeAt(0) - 'a'.charCodeAt(0);if (!crawl.children[index]) {break;}s += key[i];crawl = crawl.children[index];}if (crawl && crawl.is_end_of_word) {return s;}return "-1";}// Driver codefunction main() {const arr = ["Geeks", "Geek", "Geekss", "Geekks"];const n = arr.length;// Construct trieconst root = get_node();for (let i = 0; i < n; i++) {insert(root, arr[i]);}const queries = ["Geek", "Geeks", "Geekk", "Gee"];const q = queries.length;for (let i = 0; i < q; i++) {console.log(search(root, queries[i]));}}main(); |
Output:
Geek Geeks -1 -1
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!
