Prerequisite: Trie | (Insert and Search)
Given an array of strings words[] and a partial string str, the task is to find the strings of the given form str from the given array of string.
A partial string is a string with some missing characters. For Example: “..ta”, is a string of length 4 ending with “ta” and having two missing character at index 0 and 1.
Examples:
Input: words[] = [“moon”, “soon”, “month”, “date”, “data”], str = “..on” Output: [“moon”, “soon”] Explanation: “moon” and “soon” matches the given partial string “..on” Input: words[] = [“date”, “data”, “month”], str = “d.t.” Output: [“date”, “data”] Explanation: “date” and “data” matches the given partial string “d.t.”
Approach:
Structure of a Trie Node: The idea is to use Trie to solve the given problem Below are the steps and structures of the trie:
struct TrieNode
{
struct TrieNode* children[26];
bool endOfWord;
};
The following picture explains the construction of trie using keys given in the example above
root
/ | \
d m s
| | |
a o o
| | \ |
t o n o
/ | | | |
e a n t n
|
h
Every node is a TrieNode with pointer links to subsequent children according to the word added. Value at other pointer positions where characters are not present are marked by NULL. endOfWord are represented by blue color or leaf nodes.
Steps:
- Insert all the available words into the trie structure using the addWord() method.
- Every character of the word to be added is inserted as an individual TrieNode. The children array is an array of 26 TrieNode pointers.
- Each index representing a character from the English alphabet. If a new word is added, then for each character, it must be checked if the TrieNode pointer for that alphabet exists, then proceed further with next character, if not, a new TrieNode is created and the pointer is made to point this new node and the process repeats for next character at this new node. endOfWord is made true for the TrieNode pointed by the last character’s TrieNode pointer.
- For searching the key check for the presence of TrieNode at the index marked by the character. If present, we move down the branch and repeat the process for the next character. Similarly searching for the partial string if a ‘.’ is found, we look for all available TrieNode pointer in the children array and proceed further with each character, identified by an index, occupying the position of ‘.’ once.
- If the pointer location is empty at any point, we return not found. Else check for endOfWord at the last TrieNode, if false, we return not found, else word is found.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Dictionary Classclass Dictionary {public: // Initialize your data structure Dictionary* children[26]; bool endOfWord; // Constructor Dictionary() { this->endOfWord = false; for (int i = 0; i < 26; i++) { this->children[i] = NULL; } } // Adds a word into a data structure void addWord(string word) { // Crawl pointer points the object // in reference Dictionary* pCrawl = this; // Traverse the given array of words for (int i = 0; i < word.length(); i++) { int index = word[i] - 'a'; if (!pCrawl->children[index]) pCrawl->children[index] = new Dictionary(); pCrawl = pCrawl->children[index]; } pCrawl->endOfWord = true; } // Function that returns if the word // is in the data structure or not // A word can contain a dot character '.' // to represent any one letter void search(string word, bool& found, string curr_found = "", int pos = 0) { Dictionary* pCrawl = this; if (pos == word.length()) { if (pCrawl->endOfWord) { cout << "Found: " << curr_found << "\n"; found = true; } return; } if (word[pos] == '.') { // Iterate over every letter and // proceed further by replacing // the character in place of '.' for (int i = 0; i < 26; i++) { if (pCrawl->children[i]) { pCrawl ->children[i] ->search(word, found, curr_found + char('a' + i), pos + 1); } } } else { // Check if pointer at character // position is available, // then proceed if (pCrawl->children[word[pos] - 'a']) { pCrawl ->children[word[pos] - 'a'] ->search(word, found, curr_found + word[pos], pos + 1); } } return; } // Utility function for search operation void searchUtil(string word) { Dictionary* pCrawl = this; cout << "\nSearching for \"" << word << "\"\n"; bool found = false; pCrawl->search(word, found); if (!found) cout << "No Word Found...!!\n"; }};// Function that search the given patternvoid searchPattern(string arr[], int N, string str){ // Object of the class Dictionary Dictionary* obj = new Dictionary(); for (int i = 0; i < N; i++) { obj->addWord(arr[i]); } // Search pattern obj->searchUtil(str);}// Driver Codeint main(){ // Given an array of words string arr[] = { "data", "date", "month" }; int N = 3; // Given pattern string str = "d.t."; // Function Call searchPattern(arr, N, str);} |
Java
// Java program for the above approachimport java.util.Vector;// Dictionary Classpublic class Dictionary{ // Initialize your data structure private Dictionary[] children; private boolean endOfWord; // Constructor public Dictionary() { this.endOfWord = false; this.children = new Dictionary[26]; for (int i = 0; i < 26; i++) { this.children[i] = null; } } // Adds a word into a data structure public void addWord(String word) { // Crawl pointer points the object // in reference Dictionary pCrawl = this; // Traverse the given array of words for (int i = 0; i < word.length(); i++) { int index = word.charAt(i) - 'a'; if (pCrawl.children[index] == null) { pCrawl.children[index] = new Dictionary(); } pCrawl = pCrawl.children[index]; } pCrawl.endOfWord = true; } // Function that returns if the word // is in the data structure or not // A word can contain a dot character '.' // to represent any one letter public void search(String word, boolean[] found, String curr_found, int pos) { Dictionary pCrawl = this; if (pos == word.length()) { if (pCrawl.endOfWord) { System.out.println("Found: " + curr_found); found[0] = true; } return; } if (word.charAt(pos) == '.') { // Iterate over every letter and // proceed further by replacing // the character in place of '.' for (int i = 0; i < 26; i++) { if (pCrawl.children[i] != null) { pCrawl.children[i].search(word, found, curr_found + (char)('a' + i), pos + 1); } } } else { // Check if pointer at character // position is available, // then proceed if (pCrawl.children[word.charAt(pos) - 'a'] != null) { pCrawl.children[word.charAt(pos) - 'a'].search(word, found, curr_found + word.charAt(pos), pos + 1); } } } // Utility function for search operation public void searchUtil(String word) { boolean[] found = {false}; System.out.println("Searching for \"" + word + "\""); this.search(word, found, "", 0); if (!found[0]) { System.out.println("No Word Found...!!"); } } // Function that search the given pattern public static void searchPattern(Vector<String> words, String str) { // Object of the class Dictionary Dictionary obj = new Dictionary(); for (String word : words) { obj.addWord(word); } // Search pattern obj.searchUtil(str); } // Driver Code public static void main(String[] args) { // Given an array of words Vector<String> words = new Vector<String>(); words.add("data"); words.add("date"); words.add("month"); // Given pattern String str = "d.t."; // Function Call searchPattern(words, str); }}// This code is contributed by Aman Kumar. |
Python3
#Python code for the above approach# Dictionary Classclass Dictionary: # Initialize your data structure def __init__(self): self.children = [None] * 26 self.endOfWord = False # Adds a word into a data structure def addWord(self, word): # Crawl pointer points the object # in reference pCrawl = self # Traverse the given array of words for i in range(len(word)): index = ord(word[i]) - ord('a') if not pCrawl.children[index]: pCrawl.children[index] = Dictionary() pCrawl = pCrawl.children[index] pCrawl.endOfWord = True # Function that returns if the word # is in the data structure or not # A word can contain a dot character '.' # to represent any one letter def search(self, word, found, curr_found="", pos=0): pCrawl = self if pos == len(word): if pCrawl.endOfWord: print("Found: " + curr_found) found[0] = True return if word[pos] == '.': # Iterate over every letter and # proceed further by replacing # the character in place of '.' for i in range(26): if pCrawl.children[i]: pCrawl.children[i].search( word, found, curr_found + chr(ord('a') + i), pos + 1) else: # Check if pointer at character # position is available, # then proceed if pCrawl.children[ord(word[pos]) - ord('a')]: pCrawl.children[ord(word[pos]) - ord('a')].search( word, found, curr_found + word[pos], pos + 1) return # Utility function for search operation def searchUtil(self, word): pCrawl = self print("\nSearching for \"" + word + "\"") found = [False] pCrawl.search(word, found) if not found[0]: print("No Word Found...!!")# Function that search the given patterndef searchPattern(arr, N, str): # Object of the class Dictionary obj = Dictionary() for i in range(N): obj.addWord(arr[i]) # Search pattern obj.searchUtil(str)# Given an array of wordsarr = ["data", "date", "month"]N = 3# Given patternstr = "d.t."# Function CallsearchPattern(arr, N, str)#This code is contributed by Potta Lokesh |
C#
using System;using System.Collections.Generic;// Dictionary Classclass Dictionary{ // Initialize your data structure public Dictionary[] children; public bool endOfWord;// Constructor public Dictionary() { this.endOfWord = false; children = new Dictionary[26]; for (int i = 0; i < 26; i++) { children[i] = null; } } // Adds a word into a data structure public void AddWord(string word) { // Crawl pointer points the object // in reference Dictionary pCrawl = this; // Traverse the given array of words for (int i = 0; i < word.Length; i++) { int index = word[i] - 'a'; if (pCrawl.children[index] == null) pCrawl.children[index] = new Dictionary(); pCrawl = pCrawl.children[index]; } pCrawl.endOfWord = true; }// Function that returns if the word // is in the data structure or not // A word can contain a dot character '.' // to represent any one letter public void Search(string word, ref bool found, string currFound = "", int pos = 0) { Dictionary pCrawl = this; if (pos == word.Length) { if (pCrawl.endOfWord) { Console.WriteLine("Found: " + currFound); found = true; } return; } // Iterate over every letter and // proceed further by replacing // the character in place of '.' if (word[pos] == '.') { for (int i = 0; i < 26; i++) { if (pCrawl.children[i] != null) { pCrawl.children[i].Search(word, ref found, currFound + (char)('a' + i), pos + 1); } } } else { if (pCrawl.children[word[pos] - 'a'] != null) { pCrawl.children[word[pos] - 'a'].Search(word, ref found, currFound + word[pos], pos + 1); } } } public void SearchUtil(string word) { Dictionary pCrawl = this; Console.WriteLine("\nSearching for \"" + word + "\""); bool found = false; pCrawl.Search(word, ref found); if (!found) { Console.WriteLine("No Word Found...!!"); } }}class Program{ static void Main(string[] args) { string[] arr = { "data", "date", "month" }; int N = 3; string str = "d.t."; SearchPattern(arr, N, str); } static void SearchPattern(string[] arr, int N, string str) { Dictionary obj = new Dictionary(); for (int i = 0; i < N; i++) { obj.AddWord(arr[i]); } // Function Call obj.SearchUtil(str); }} |
Javascript
// Dictionary Classclass Dictionary {// Initialize your data structureconstructor() {this.children = new Array(26).fill(null);this.endOfWord = false;}// Adds a word into a data structureaddWord(word) {// Crawl pointer points the object// in referencelet pCrawl = this;// Traverse the given array of wordsfor (let i = 0; i < word.length; i++) { const index = word[i].charCodeAt(0) - "a".charCodeAt(0); if (!pCrawl.children[index]) { pCrawl.children[index] = new Dictionary(); } pCrawl = pCrawl.children[index];}pCrawl.endOfWord = true;}// Function that returns if the word// is in the data structure or not// A word can contain a dot character '.'// to represent any one lettersearch(word, found, curr_found="", pos=0) {let pCrawl = this;if (pos === word.length) { if (pCrawl.endOfWord) { console.log("Found: " + curr_found + "<br>"); found[0] = true; } return;}if (word[pos] === '.') { // Iterate over every letter and // proceed further by replacing // the character in place of '.' for (let i = 0; i < 26; i++) { if (pCrawl.children[i]) { pCrawl.children[i].search( word, found, curr_found + String.fromCharCode("a".charCodeAt(0) + i), pos + 1 ); } }} else { // Check if pointer at character // position is available, // then proceed if (pCrawl.children[word[pos].charCodeAt(0) - "a".charCodeAt(0)]) { pCrawl.children[word[pos].charCodeAt(0) - "a".charCodeAt(0)].search( word, found, curr_found + word[pos], pos + 1 ); }}return;}// Utility function for search operationsearchUtil(word) {let pCrawl = this;console.log(`\nSearching for "${word}" <br>`);let found = [false];pCrawl.search(word, found);if (!found[0]) { console.log("No Word Found...!!");}}}// Function that search the given patternfunction searchPattern(arr, N, str) {// Object of the class Dictionarylet obj = new Dictionary();for (let i = 0; i < N; i++) {obj.addWord(arr[i]);}// Search patternobj.searchUtil(str);}// Given an array of wordslet arr = ["data", "date", "month"];let N = 3;// Given patternlet str = "d.t.";// Function CallsearchPattern(arr, N, str); |
Output:
Searching for "d.t." Found: data Found: date
Time Complexity: O(M*log(N)), where N is the number of strings and M is length of the given pattern
Auxiliary Space: O(26*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!
