Given a set of strings S and a string P, the task is to print all strings from the set with the suffix P. Examples:
Input: S = {“neveropen”, “neveropen”, “geek”, “newneveropen”, “friendsonneveropen”, “toppergeek”} P = “neveropen”
Output: neveropen friendsonneveropen neveropen newneveropen
Input: S = {“wideworld”, “webworld”, “classicword”, “world”, “worldclass”} P = “world”
Output: wideworld webworld world
Approach: The idea is to use Pattern Searching using a Trie of all Suffixes.
- Store the strings in a Trie in reverse order.
- Reverse the string P and search for it using the standard Trie search algorithm.
- Check if the reversed string P is itself a word in Trie, which be checked by seeing if the last matching node has isEndWord flag set.
- Otherwise, if the reversed string P forms a suffix, then recursively print all nodes under the subtree of the last matching node.
Below is the implementation of the above approach:
C++
// C++ code to print all// strings from a given set// with suffix P#include <bits/stdc++.h>using namespace std;#define CHILD (26)// Converts key current character// into index use only 'a' through// 'z' and lower case#define CHAR_TO_INDEX(c) (int)(c - 'a')// Trie nodestruct TrieNode { struct TrieNode* children[CHILD]; // isWordEnd is true if the node // represents end of a word bool isWordEnd;};// Function to reverse a stringstring reverseStr(string str){ int n = str.length(); // Swap character starting from // two corners for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); return str;}// Returns new trie nodestruct TrieNode* getNode(void){ struct TrieNode* pNode = new TrieNode; pNode->isWordEnd = false; for (int i = 0; i < CHILD; i++) pNode->children[i] = NULL; return pNode;}// If not present, inserts key into// trie. If the key is suffix of trie// node, just mark leaf nodevoid insert(struct TrieNode* root, const string key){ struct TrieNode* pCrawl = root; for (int level = 0; level < key.length(); level++) { int index = CHAR_TO_INDEX(key[level]); if (!pCrawl->children[index]) pCrawl->children[index] = getNode(); pCrawl = pCrawl->children[index]; } // Mark last node as leaf pCrawl->isWordEnd = true;}// Returns true if key presents in// the trie, else falsebool search(struct TrieNode* root, const string key){ int length = key.length(); struct TrieNode* pCrawl = root; for (int level = 0; level < length; level++) { int index = CHAR_TO_INDEX(key[level]); if (!pCrawl->children[index]) return false; pCrawl = pCrawl->children[index]; } return (pCrawl != NULL && pCrawl->isWordEnd);}// Returns 0 if current node has// a child// If all children are NULL, return 1bool isLastNode(struct TrieNode* root){ for (int i = 0; i < CHILD; i++) if (root->children[i]) return 0; return 1;}// Recursive function to print strings// having given suffixvoid printStrings(struct TrieNode* root, string currsuffix){ // If a string with currsuffix // is found if (root->isWordEnd) { cout << reverseStr(currsuffix); cout << endl; reverseStr(currsuffix); } // All children struct node // pointers are NULL if (isLastNode(root)) return; for (int i = 0; i < CHILD; i++) { if (root->children[i]) { // Append current character // to currsuffix string currsuffix.push_back(97 + i); // recur over the rest printStrings(root->children[i], currsuffix); // remove last character currsuffix.pop_back(); } }}// print strings with given suffixint printStringsWithGivenSuffix( TrieNode* root, const string query){ struct TrieNode* pCrawl = root; // Check if suffix is present // and find the node (of last // level) with last character // of given string. int level; int n = query.length(); for (level = 0; level < n; level++) { int index = CHAR_TO_INDEX(query[level]); // no string in the Trie has // this suffix if (!pCrawl->children[index]) return 0; pCrawl = pCrawl->children[index]; } // If suffix is present as a word. bool isWord = (pCrawl->isWordEnd == true); // If suffix is last node of // tree (has no children) bool isLast = isLastNode(pCrawl); // If suffix is present as a word, // but there is no subtree below // the last matching node. if (isWord && isLast) { cout << query << endl; return -1; } // If there are nodes below // last matching character. if (!isLast) { string suffix = query; printStrings(pCrawl, suffix); return 1; }}// Driver Codeint main(){ struct TrieNode* root = getNode(); vector<string> S = { "neveropen", "neveropen", "geek", "newneveropen", "friendsonneveropen", "toppergeek" }; for (string str : S) { insert(root, reverseStr(str)); } string P = "eek"; printStringsWithGivenSuffix( root, reverseStr(P)); return 0;} |
Java
// java code to print all// strings from a given set// with suffix Pimport java.util.*;public class GFG { // Converts key current character // into index use only 'a' through // 'z' and lower case static final int CHILD = 26; // Trie node static class TrieNode { TrieNode[] children = new TrieNode[CHILD]; // isWordEnd is true if the node // represents end of a word boolean isWordEnd; } // Function to reverse a string static String reverseStr(String str) { int n = str.length(); char[] chars = str.toCharArray(); for (int i = 0; i < n / 2; i++) { char temp = chars[i]; chars[i] = chars[n - i - 1]; chars[n - i - 1] = temp; } return new String(chars); } // Returns new trie node static TrieNode getNode() { TrieNode pNode = new TrieNode(); pNode.isWordEnd = false; for (int i = 0; i < CHILD; i++) pNode.children[i] = null; return pNode; } // If not present, inserts key into // trie. If the key is suffix of trie // node, just mark leaf node static void insert(TrieNode root, String key) { TrieNode pCrawl = root; for (int level = 0; level < key.length(); level++) { int index = key.charAt(level) - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = getNode(); pCrawl = pCrawl.children[index]; } // Mark last node as leaf pCrawl.isWordEnd = true; } // Returns true if key presents in // the trie, else false static boolean search(TrieNode root, String key) { int length = key.length(); TrieNode pCrawl = root; for (int level = 0; level < length; level++) { int index = key.charAt(level) - 'a'; if (pCrawl.children[index] == null) return false; pCrawl = pCrawl.children[index]; } return (pCrawl != null && pCrawl.isWordEnd); } // Returns 0 if current node has // a child // If all children are NULL, return 1 static boolean isLastNode(TrieNode root) { for (int i = 0; i < CHILD; i++) if (root.children[i] != null) return false; return true; } // Recursive function to print strings // having given suffix static void printStrings(TrieNode root, String currsuffix) { if (root.isWordEnd) { System.out.println(reverseStr(currsuffix)); currsuffix = reverseStr(currsuffix); } if (isLastNode(root)) return; for (int i = 0; i < CHILD; i++) { if (root.children[i] != null) { currsuffix += (char) ('a' + i); printStrings(root.children[i], currsuffix); currsuffix = currsuffix.substring(0, currsuffix.length() - 1); } } } // check string withg given suffix static int printStringsWithGivenSuffix(TrieNode root, String query) { TrieNode pCrawl = root; // Check if suffix is present // and find the node (of last // level) with last character // of given string. int level; int n = query.length(); for (level = 0; level < n; level++) { int index = query.charAt(level) - 'a'; if (pCrawl.children[index] == null) return 0; pCrawl = pCrawl.children[index]; } boolean isWord = pCrawl.isWordEnd; boolean isLast = isLastNode(pCrawl); if (isWord && isLast) { System.out.println(query); return -1; } if (!isLast) { String suffix = query; printStrings(pCrawl, suffix); return 1; } return 0; } // Driver code public static void main(String[] args) { TrieNode root = getNode(); List<String> S = Arrays.asList("neveropen", "neveropen", "geek", "newneveropen", "friendsonneveropen", "toppergeek"); for (String str : S) { insert(root, reverseStr(str)); } String P = "eek"; printStringsWithGivenSuffix(root, reverseStr(P)); }}// this code is contributed by bhardwajji |
Python
# Python3 code for the above programclass TrieNode(): def __init__(self): # Initialize one node for trie self.children = {} self.last = Falsedef reverse(s): str = "" for i in s: str = i + str return strclass Trie(): def __init__(self): # Initialize the trie structure self.root = TrieNode() self.word_list = [] def formTrie(self, keys): # Forms a trie structure # with the given set of # strings if it does not # exists already else it # merges the key into it # by extending the # structure as required for key in keys: # inserting one key # to the trie. self.insert(key) def insert(self, key): # Inserts a key into # trie if it does not # exist already. And if # the key is a suffix # of the trie node, just # marks it as leaf node. node = self.root for a in list(key): if not node.children.get(a): node.children[a] = TrieNode() node = node.children[a] node.last = True def search(self, key): # Searches the given key # in trie for a full match # and returns True on # success else returns False node = self.root found = True for a in list(key): if not node.children.get(a): found = False break node = node.children[a] return node and node.last and found def printStrings(self, node, word): # Method to recursively # traverse the trie # and return a whole word if node.last: self.word_list.append(word) for a, n in node.children.items(): self.printStrings(n, word + a) def printStringsWithGivenSuffix(self, key): # Returns all the words in # the trie whose common # suffix is the given key # thus listing out all # the strings node = self.root not_found = False temp_word = '' for a in list(key): if not node.children.get(a): not_found = True break temp_word += a node = node.children[a] if not_found: return 0 elif node.last and not node.children: return -1 self.printStrings(node, temp_word) for s in self.word_list: print(reverse(s)) return 1# Driver Code # keys to form the trie structurekeys = [reverse("neveropen"), reverse("neveropen"), reverse("geek"), reverse("newneveropen"), reverse("friendsonneveropen"), reverse("toppergeek")] # key key = "eek"status = ["Not found", "Found"] # creating trie object t = Trie() # creating the trie structure # with the given set of stringst.formTrie(keys) # print string having suffix 'P'# our trie structurecomp = t.printStringsWithGivenSuffix(reverse(key)) |
Javascript
// Javascript code to print all// strings from a given set// with suffix Pconst CHILD = 26;// Converts key current character// into index use only 'a' through// 'z' and lower caseconst CHAR_TO_INDEX = (c) => c.charCodeAt(0) - 'a'.charCodeAt(0);// Trie nodeclass TrieNode { constructor() {this.children = Array(CHILD).fill(null);// isWordEnd is true if the node// represents end of a wordthis.isWordEnd = false; }}// Function to reverse a stringconst reverseStr = (str) => str.split('').reverse().join('');// Returns new trie nodeconst getNode = () => new TrieNode();// If not present, inserts key into// trie. If the key is suffix of trie// node, just mark leaf nodeconst insert = (root, key) => { let pCrawl = root; for (let i = 0; i < key.length; i++) {const index = CHAR_TO_INDEX(key[i]);if (!pCrawl.children[index]) { pCrawl.children[index] = getNode();}pCrawl = pCrawl.children[index]; } // Mark last node as leaf pCrawl.isWordEnd = true;};// Returns true if key presents in// the trie, else falseconst search = (root, key) => { const length = key.length; let pCrawl = root; for (let i = 0; i < length; i++) {const index = CHAR_TO_INDEX(key[i]);if (!pCrawl.children[index]) { return false;}pCrawl = pCrawl.children[index]; } return pCrawl !== null && pCrawl.isWordEnd;};// Returns 0 if current node has// a child// If all children are NULL, return 1const isLastNode = (root) => { for (let i = 0; i < CHILD; i++) {if (root.children[i]) { return false;} } return true;};// Recursive function to print strings// having given suffixconst printStrings = (root, currsuffix) => { // If a string with currsuffix // is found if (root.isWordEnd) { console.log(reverseStr(currsuffix)+"<br>"); } // All children struct node// pointers are NULL if (isLastNode(root)) {return; } for (let i = 0; i < CHILD; i++) {if (root.children[i]) { // Append current character // to currsuffix string currsuffix += String.fromCharCode(97 + i); // recur over the rest printStrings(root.children[i], currsuffix); // remove last character currsuffix = currsuffix.slice(0, -1);} }};// print strings with given suffixconst printStringsWithGivenSuffix = (root, query) => { let pCrawl = root;// Check if suffix is present// and find the node (of last// level) with last character// of given string. for (let i = 0; i < query.length; i++) {const index = CHAR_TO_INDEX(query[i]);// no string in the Trie has// this suffixif (!pCrawl.children[index]) { return 0;}pCrawl = pCrawl.children[index]; } // If suffix is present as a word. const isWord = pCrawl.isWordEnd; // If suffix is last node of // tree (has no children) const isLast = isLastNode(pCrawl); // If suffix is present as a word, // but there is no subtree below // the last matching node. if (isWord && isLast) {console.log(query+"<br>");return -1; } // If there are nodes below // last matching character. if (!isLast) {let suffix = query;printStrings(pCrawl, suffix);return 1; }};// Driver Codeconst root = getNode();const S = [ 'neveropen', 'neveropen', 'geek', 'newneveropen', 'friendsonneveropen', 'toppergeek',];for (const str of S) { insert(root, reverseStr(str));}const P = 'eek';printStringsWithGivenSuffix( root, reverseStr(P)); //This code is contributed by Pushpesh Raj. |
C#
// C# program to print all// strings from a given set// with suffix Pusing System;using System.Collections.Generic;public class GFG { // Converts key current character // into index use only 'a' through // 'z' and lower case const int CHILD = 26; // Trie node class TrieNode { public TrieNode[] children = new TrieNode[CHILD]; // isWordEnd is true if the node // represents end of a word public bool isWordEnd; } // Function to reverse a string static string ReverseStr(string str) { int n = str.Length; char[] chars = str.ToCharArray(); for (int i = 0; i < n / 2; i++) { char temp = chars[i]; chars[i] = chars[n - i - 1]; chars[n - i - 1] = temp; } return new string(chars); } // Returns new trie node static TrieNode GetNode() { TrieNode pNode = new TrieNode(); pNode.isWordEnd = false; for (int i = 0; i < CHILD; i++) pNode.children[i] = null; return pNode; } // If not present, inserts key into // trie. If the key is suffix of trie // node, just mark leaf node static void Insert(TrieNode root, string key) { TrieNode pCrawl = root; for (int level = 0; level < key.Length; level++) { int index = key[level] - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = GetNode(); pCrawl = pCrawl.children[index]; } // Mark last node as leaf pCrawl.isWordEnd = true; } // Returns true if key presents in // the trie, else false static bool Search(TrieNode root, string key) { int length = key.Length; TrieNode pCrawl = root; for (int level = 0; level < length; level++) { int index = key[level] - 'a'; if (pCrawl.children[index] == null) return false; pCrawl = pCrawl.children[index]; } return (pCrawl != null && pCrawl.isWordEnd); } // Returns 0 if current node has // a child // If all children are NULL, return 1 static bool IsLastNode(TrieNode root) { for (int i = 0; i < CHILD; i++) if (root.children[i] != null) return false; return true; } // Recursive function to print strings // having given suffix static void PrintStrings(TrieNode root, string currsuffix) { if (root.isWordEnd) { Console.WriteLine(ReverseStr(currsuffix)); currsuffix = ReverseStr(currsuffix); } if (IsLastNode(root)) return; for (int i = 0; i < CHILD; i++) { if (root.children[i] != null) { currsuffix += (char)('a' + i); PrintStrings(root.children[i], currsuffix); currsuffix = currsuffix.Substring( 0, currsuffix.Length - 1); } } } // check string withg given suffix static int PrintStringsWithGivenSuffix(TrieNode root, string query) { TrieNode pCrawl = root; // Check if suffix is present // and find the node (of last // level) with last character // of given string. int level; int n = query.Length; for (level = 0; level < n; level++) { int index = query[level] - 'a'; if (pCrawl.children[index] == null) return 0; pCrawl = pCrawl.children[index]; } bool isWord = pCrawl.isWordEnd; bool isLast = IsLastNode(pCrawl); if (isWord && isLast) { Console.WriteLine(query); return -1; } if (!isLast) { string suffix = query; PrintStrings(pCrawl, suffix); return 1; } return 0; } // Driver Code static void Main(string[] args) { TrieNode root = GetNode(); List<string> S = new List<string>{ "neveropen", "neveropen", "geek", "newneveropen", "friendsonneveropen", "toppergeek" }; foreach(string str in S) { Insert(root, ReverseStr(str)); } string P = "eek"; PrintStringsWithGivenSuffix(root, ReverseStr(P)); }}// This code is contributed by Prince kumar |
Output:
geek toppergeek
Time Complexity : O(N * L)
Auxiliary Space : O(N)
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!
