Given two arrays of strings containing words[] and queries[] having N and Q strings respectively, the task is to find the number of strings from words[] having queries[i] as the prefix for all the strings in queries[].
Examples:
Input: words[] = { “neveropen”, “neveropen”, “neveropen for neveropen”, “string”, “strong” }, queries[] = { “geek”, “gel”, “str” }
Output: 3, 0, 2
Explanation:
1st query “geek” is present in 3 words in the list as a prefix, { “geekf”, “geeks”, “geeksforneveropen” }
2nd query “gel” is not present in any word in the list as a prefix
3rd query “str” is present in 2 words in the list as a prefix, {“string”, “strong”}Input: words[] = { “apple”, “app”, “ape”, “alien”, “a”, “box”, “boxing” }, queries[] = { “a”, “ap”, “b”, “app”, “book” }
Output: 5, 3, 2, 2, 0
Explanation:
1st query “a” is present in 5 words in the list as a prefix, { “apple”, “app”, “ape”, “alien”, “a” }
2nd query “ap” is present in 3 words in the list as a prefix, { “apple”, “app”, “ape” }
3rd query “b” is present in 2 words in the list as a prefix, {“box”, “boxing”}
4th query “app” is present in 2 words in the list as a prefix, {“apple”, “app“}
5th query “book” is not present in any word in the list as a prefix
Naive Approach: The problem can be solved based on the following idea:
For each query traverse through every word in the list and check whether the word has a prefix as current query or not.
- Create a dummy vector ans, to store the resultant array.
- Start traversing queries[] and initialize a counter variable count to store the count of words that have prefixes as the current query.
- If the size of any word at any ith iteration is less than the size of the query, skip the iteration.
- If the prefix is found in words[] then increment the counter variable.
- Push count of prefixes in the vector ans.
- Return the ans.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return an array containing// the number of words having the given prefix// for each queryvector<int> GeekAndString(vector<string>& words, vector<string>& Queries){ vector<int> ans; for (string x : Queries) { // To count number of // matching prefixes in word array int count = 0; for (string word : words) { if (word.size() < x.size()) continue; // If prefix found then increment counter if (word.substr(0, x.size()) == x) count++; } ans.push_back(count); } return ans;}// Driver Codeint main(){ vector<string> words = { "geekf", "neveropen", "neveropen", "string", "strong" }; vector<string> queries = { "geek", "gel", "str" }; // Function call vector<int> ans = GeekAndString(words, queries); for (int x : ans) cout << x << " "; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { String[] words = { "geekf", "neveropen", "neveropen", "string", "strong" }; String[] queries = { "geek", "gel", "str" }; // Function call ArrayList<Integer> ans = GeekAndString(words, queries); for (int count : ans) { System.out.print(count + " "); } System.out.println(); } // Function to return an array // containing the number of words // having given prefix for each query public static ArrayList<Integer> GeekAndString(String[] Li, String[] Queries) { ArrayList<Integer> answer = new ArrayList<>(); for (String x : Queries) { int count = 0; for (String word : Li) { if (word.length() < x.length()) continue; if (x.equals( word.substring(0, x.length()))) { count++; } } answer.add(count); } return answer; }} |
Python3
# Python3 code to implement the approach# Function to return an array containing# the number of words having the given prefix# for each querydef GeekAndString(words, Queries) : ans = []; for x in Queries : # To count number of number of # matching prefixes in word array count = 0; for word in words : if len(word) < len(x) : continue; # If prefix found then increment counter if (word[0 : len(x)] == x) : count += 1; ans.append(count); return ans;# Driver Codeif __name__ == "__main__" : words = [ "geekf", "neveropen", "neveropen","string", "strong" ]; queries = [ "geek", "gel", "str" ]; # Function call ans = GeekAndString(words, queries); for x in ans: print(x,end=" "); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections;class GFG { // Driver Code public static void Main(string[] args) { string[] words = { "geekf", "neveropen", "neveropen", "string", "strong" }; string[] queries = { "geek", "gel", "str" }; // Function call ArrayList ans = GeekAndString(words, queries); foreach(int count in ans) { Console.Write(count + " "); } Console.WriteLine(); } // Function to return an array // containing the number of words // having given prefix for each query public static ArrayList GeekAndString(string[] Li, string[] Queries) { ArrayList answer = new ArrayList(); foreach(string x in Queries) { int count = 0; foreach(string word in Li) { if (word.Length < x.Length) continue; if (x.Equals(word.Substring(0, x.Length))) { count++; } } answer.Add(count); } return answer; }}// This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code to implement the approach// Function to return an array containing// the number of words having the given prefix// for each queryconst GeekAndString = (words, Queries) => { let ans = []; for (let x in Queries) { // To count number of number of // matching prefixes in word array let count = 0; for (let word in words) { if (words[word].length < Queries[x].length) continue; // If prefix found then increment counter if (words[word].substring(0, Queries[x].length) == Queries[x]) count++; } ans.push(count); } return ans;}// Driver Codelet words = ["geekf", "neveropen", "neveropen", "string", "strong"];let queries = ["geek", "gel", "str"];// Function calllet ans = GeekAndString(words, queries);for (let x in ans) console.log(`${ans[x]} `);// This code is contributed by rakeshsahni |
Output
3 0 2
Time Complexity: O(N * Q * M), where M = maximum length of a string in queries[]
Auxiliary Space: O(N)
Efficient approach: The problem can be solved efficiently on the basis of the following approach
We have to use such a data structure to match the string to find out if it is prefix of another string in optimal time. Trie can help us in this problem.
Build a trie and insert the strings of word[] in the trie. where each node will also keep a count of strings with that prefix. Then while traversing through queries[] find the prefix and the count associated with it. The structure of a trie node will be like the following:
- children: This field is used for mapping from a character to the next level trie node
- isEndOfWord: This field is used to distinguish the node as end of word node
- num: This field is used to count the number of times a node is visited during insertion in trie
Follow the steps mentioned below to implement the idea:
- Insert the list of strings in trie such that every string in the list is inserted as an individual trie node.
- During inserting update all the fields in every node of the trie
- For each query, traverse the trie till we reach the last character of the given prefix queries[i].
- The value of the num field in the last node of the prefix is the count of strings of words[] having the given prefix.
- For each query, store this num, in an answer vector.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int x;// Structure of a trie nodestruct trie { int cnt; trie* ch[26]; trie() { cnt = 0; for (int i = 0; i < 26; i++) ch[i] = NULL; }};// Function to build the trievoid build(vector<string>& a, trie* root){ trie* temp; for (int i = 0; i < x; i++) { temp = root; for (int j = 0; j < a[i].size(); j++) { if (temp->ch[a[i][j] - 'a'] == NULL) temp->ch[a[i][j] - 'a'] = new trie(); temp->ch[a[i][j] - 'a']->cnt += 1; temp = temp->ch[a[i][j] - 'a']; } }}// Function to find a string in the trieint find(string s, trie* root){ for (int i = 0; i < s.size(); i++) { if (root->ch[s[i] - 'a'] == NULL) return 0; root = root->ch[s[i] - 'a']; } return root->cnt;}// Function to get the given number of string// having the same prefix as the queryvector<int> prefixCount(int N, int Q, vector<string>& list, vector<string>& query){ vector<int> res; x = N; trie* root = new trie(); build(list, root); for (int i = 0; i < Q; i++) res.push_back(find(query[i], root)); return res;}// Driver Codeint main(){ vector<string> words = { "geekf", "neveropen", "neveropen", "string", "strong" }; vector<string> queries = { "geek", "gel", "str" }; // Function call vector<int> ans = prefixCount( words.size(), queries.size(), words, queries); for (int count : ans) cout << count << " "; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { String[] words = { "geekf", "neveropen", "neveropen", "string", "strong" }; String[] queries = { "geek", "gel", "str" }; // Function call ArrayList<Integer> ans = GeekAndString(words, queries); for (int count : ans) System.out.print(count + " "); } // Function to get the given number of string // having the same prefix as the query public static ArrayList<Integer> GeekAndString(String[] Li, String[] Queries) { ArrayList<Integer> answer = new ArrayList<>(); Trie trie = new Trie(); for (String word : Li) { trie.inert(word); } for (String word : Queries) { answer.add(trie.query(word)); } return answer; }}// Structure of a trie nodeclass TrieNode { TrieNode[] links; int counter; TrieNode() { this.links = new TrieNode[26]; this.counter = 0; }}// Structure of a trieclass Trie { private TrieNode root; Trie() { this.root = new TrieNode(); } // Function to insert the string in the trie public void inert(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int pos = (word.charAt(i) - 'a'); if (node.links[pos] == null) { node.links[pos] = new TrieNode(); } node = node.links[pos]; node.counter = node.counter + 1; } } // Function to find answer for each query public int query(String word) { TrieNode node = root; for (int i = 0; i < word.length(); i++) { int pos = (word.charAt(i) - 'a'); if (node.links[pos] == null) { return 0; } node = node.links[pos]; } return node.counter; }} |
Python
# Python code to implement the above approach# Structure of a trie nodeclass Trie: def __init__(self): self.cnt = 0 self.ch = [None] * 26# Function to build the triedef build(a, root): temp = None for i in range(len(a)): temp = root for j in range(len(a[i])): if not temp.ch[ord(a[i][j]) - ord('a')]: temp.ch[ord(a[i][j]) - ord('a')] = Trie() temp.ch[ord(a[i][j]) - ord('a')].cnt += 1 temp = temp.ch[ord(a[i][j]) - ord('a')]# Function to find a string in the triedef find(s, root): for i in range(len(s)): if not root.ch[ord(s[i]) - ord('a')]: return 0 root = root.ch[ord(s[i]) - ord('a')] return root.cnt# Function to get the given number of string# having the same prefix as the querydef prefixCount(N, Q, list, query): res = [] root = Trie() build(list, root) for i in range(Q): res.append(find(query[i], root)) return res# Driver Codewords = ["geekf", "neveropen", "neveropen","string", "strong"]queries = ["geek", "gel", "str"]# Function callans = prefixCount(len(words), len(queries), words, queries)print(ans) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;// Structure of a trie nodepublic class TrieNode { public TrieNode[] links; public int counter; public TrieNode() { this.links = new TrieNode[26]; this.counter = 0; }}// Structure of a triepublic class Trie { private TrieNode root; public Trie() { this.root = new TrieNode(); } // Function to insert the string in the trie public void Insert(string word) { TrieNode node = root; for (int i = 0; i < word.Length; i++) { int pos = (word[i] - 'a'); if (node.links[pos] == null) { node.links[pos] = new TrieNode(); } node = node.links[pos]; node.counter = node.counter + 1; } } // Function to find answer for each query public int Query(string word) { TrieNode node = root; for (int i = 0; i < word.Length; i++) { int pos = (word[i] - 'a'); if (node.links[pos] == null) { return 0; } node = node.links[pos]; } return node.counter; }}public class GFG { // Function to get the given number of string // having the same prefix as the query static List<int> GeekAndString(string[] Li, string[] Queries) { List<int> answer = new List<int>(); Trie trie = new Trie(); foreach(string word in Li) { trie.Insert(word); } foreach(string word in Queries) { answer.Add(trie.Query(word)); } return answer; } static public void Main() { // Code string[] words = { "geekf", "neveropen", "neveropen", "string", "strong" }; string[] queries = { "geek", "gel", "str" }; // Function call List<int> ans = GeekAndString(words, queries); foreach(int count in ans) Console.Write(count + " "); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approachlet x;// Structure of a trie nodeclass trie { constructor(){ this.cnt=0; this.ch= new Array(26); }};// Function to build the triefunction build( a, root){ let temp=new trie(); for (let i = 0; i < x; i++) { temp = root; for (let j = 0; j < a[i].length; j++) { let x= a[i].charCodeAt(j)-97; if (temp.ch[x] == null) temp.ch[x] = new trie(); temp.ch[x].cnt += 1; temp = temp.ch[x]; } }}// Function to find a string in the triefunction find( s, root){ for (let i = 0; i < s.length; i++) { let x= s.charCodeAt(i)-97; if (root.ch[x] == null) return 0; root = root.ch[x]; } return root.cnt;}// Function to get the given number of string// having the same prefix as the queryfunction prefixCount(N, Q,list, query){ let res=[]; x = N; let root = new trie(); build(list, root); for (let i = 0; i < Q; i++) res.push(find(query[i], root)); return res;}// Driver Code let words = [ "geekf", "neveropen", "neveropen", "string", "strong" ]; let queries = [ "geek", "gel", "str" ]; // Function call let ans = prefixCount( words.length, queries.length, words, queries); console.log(ans); // This code is contributed by garg28harsh. |
Output
3 0 2
Time Complexity: O(Q * x + N*L), Where x is the longest word in the query, and L = length of the longest word inserted in the trie.
Auxiliary Space: O(N * List [i])
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!
