Count of given Strings in 2D character Array using Trie
Counting the number of occurrences of a given string in a 2D character array using a Trie.
Examples:
Input: vector<string> grid = {“abcde”, “fghij”, “xyabc”, “klmno”,}; string word = “abc”;
Output: 2
Explanation: abc occurs twice in “abcde”, “xyabc”Input: vector<string> grid = {“abcde”, “fghij”, “xyabc”, “klmno”,}; string word = “klm”;
Output: 1
Explanation: klm occurs once in “klmno”
Approach:
Counting the number of occurrences of a given string in a 2D character array using a Trie approach involves building a Trie data structure from the 2D array and then searching for the given string in the Trie.
- We first build a Trie from the given word.
- Then, we iterate through the 2D character array and construct substrings from each starting position.
- If a substring exists in the Trie, we increment the count.
- Finally, we return the count, which represents the number of occurrences of the given string in the 2D array.
Implementation:
C++
#include <iostream> #include <vector> using namespace std; const int ALPHABET_SIZE = 26; // Trie Node struct TrieNode { TrieNode* children[ALPHABET_SIZE]; bool isEndOfWord; TrieNode() { isEndOfWord = false ; for ( int i = 0; i < ALPHABET_SIZE; i++) { children[i] = nullptr; } } }; // Trie class class Trie { public : Trie() { root = new TrieNode(); } // Insert a word into the Trie void insert( const string& word) { TrieNode* current = root; for ( char c : word) { int index = c - 'a' ; if (!current->children[index]) { current->children[index] = new TrieNode(); } current = current->children[index]; } current->isEndOfWord = true ; } // Search for a word in the Trie bool search( const string& word) { TrieNode* current = root; for ( char c : word) { int index = c - 'a' ; if (!current->children[index]) { return false ; } current = current->children[index]; } return current->isEndOfWord; } private : TrieNode* root; }; // Count occurrences of a word in a 2D array using Trie int countWordsIn2DArray(vector<string>& grid, const string& word) { int rows = grid.size(); int cols = grid[0].size(); int count = 0; Trie trie; trie.insert(word); for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { string current = ""; for ( int k = j; k < cols; k++) { current += grid[i][k]; if (trie.search(current)) { count++; } } } } return count; } int main() { vector<string> grid = { "abcde", "fghij", "xyabc", "klmno", }; string word = "abc"; int result = countWordsIn2DArray(grid, word); cout << result << endl; return 0; } |
Java
import java.io.*; import java.util.Arrays; // TrieNode class represents a node in the Trie data structure class TrieNode { private TrieNode[] children; // An array to store references to child nodes private boolean isEndOfWord; // Indicates if this node marks the end of a word public TrieNode() { children = new TrieNode[ 26 ]; // Assuming lowercase English letters Arrays.fill(children, null ); // Initialize the children array to null isEndOfWord = false ; // Initialize the end of word flag to false } public TrieNode[] getChildren() { return children; } public boolean isEndOfWord() { return isEndOfWord; } public void setEndOfWord( boolean endOfWord) { isEndOfWord = endOfWord; } } // Trie class represents a Trie data structure class Trie { private TrieNode root; public Trie() { root = new TrieNode(); // Initialize the root node } // Insert a word into the Trie public void insert(String word) { TrieNode current = root; // Start from the root for ( char c : word.toCharArray()) { int index = c - 'a' ; // Calculate the index for the character 'a' to 'z' if (current.getChildren()[index] == null ) { current.getChildren()[index] = new TrieNode(); // Create a new node if it doesn't exist } current = current.getChildren()[index]; // Move to the child node } current.setEndOfWord( true ); // Mark the last node as the end of the word } // Search for a word in the Trie public boolean search(String word) { TrieNode current = root; // Start from the root for ( char c : word.toCharArray()) { int index = c - 'a' ; // Calculate the index for the character 'a' to 'z' if (current.getChildren()[index] == null ) { return false ; // If a character is not found in the Trie, the word is not present } current = current.getChildren()[index]; // Move to the child node } return current.isEndOfWord(); // Check if the last node marks the end of a word } } public class WordSearchIn2DArray { // Count the number of occurrences of a word in a 2D grid of characters public static int countWordsIn2DArray(String[] grid, String word) { int rows = grid.length; int cols = grid[ 0 ].length(); int count = 0 ; Trie trie = new Trie(); // Create a Trie data structure trie.insert(word); // Insert the target word into the Trie // Iterate through the grid to search for the word for ( int i = 0 ; i < rows; i++) { for ( int j = 0 ; j < cols; j++) { StringBuilder current = new StringBuilder(); // A StringBuilder to build the current word for ( int k = j; k < cols; k++) { current.append(grid[i].charAt(k)); // Append characters from the grid if (trie.search(current.toString())) { count++; // If a matching word is found, increment the count } } } } return count; } public static void main(String[] args) { String[] grid = { "abcde" , "fghij" , "xyabc" , "klmno" }; String word = "abc" ; int result = countWordsIn2DArray(grid, word); System.out.println(result); // Print the result } } |
Python3
# Python program for the above approach # Create a trie node structure class TrieNode: # Trie node class def __init__( self ): self .children = [ None ] * 26 # isEndOfWord is True if it's end of a word self .isEndOfWord = False # Trie data structure class class Trie: # initialize the root def __init__( self ): self .root = self .getNode() # Returns a new trie node def getNode( self ): return TrieNode() # Converts the current character into an index def _charToIndex( self , ch): return ord (ch) - ord ( 'a' ) # Insert a string into the trie def insert( self , word): # Start at the root of the trie pCrawl = self .root length = len (word) # Iterate through each character in the word for i in range (length): # Convert the current character to an index index = self ._charToIndex(word[i]) # If the current character is not present # create it if not pCrawl.children[index]: pCrawl.children[index] = self .getNode() # Move to the child node and continue pCrawl = pCrawl.children[index] # Mark last node as end of the word pCrawl.isEndOfWord = True # Search for a string in the trie def search( self , word): # Start at the root of the trie pCrawl = self .root length = len (word) # Iterate through each character in the target word for i in range (length): # Convert the current character to an index index = self ._charToIndex(word[i]) if not pCrawl.children[index]: return False # Move to the child node and continue # the search process pCrawl = pCrawl.children[index] return pCrawl.isEndOfWord # Count string occurrences in a 2D array def countWordsIn2DArray(grid, word): # Calculate the row and column length rows = len (grid) cols = len (grid[ 0 ]) count = 0 # Initialize the trie data structure trie = Trie() trie.insert(word) # Loop through all possible trie combinations for i in range (rows): for j in range (cols): current = "" for k in range (j,cols): current + = grid[i][k] # Call the search method to check # if the string is present if trie.search(current): # if present, increment count count + = 1 return count # Driver function def main(): grid = [ "abcde" , "fghij" , "xyabc" , "klmno" ,] word = "abc" result = countWordsIn2DArray(grid, word) print (result) if __name__ = = '__main__' : main() # This code is contributed by Omkar N. Chorge (omkarchorge10) |
C#
// C# Code Addition using System; using System.Collections.Generic; namespace WordSearchIn2DArray { // TrieNode class represents a node in the Trie data structure class TrieNode { private TrieNode[] children; // An array to store references to child nodes private bool isEndOfWord; // Indicates if this node marks the end of a word public TrieNode() { children = new TrieNode[26]; // Assuming lowercase English letters Array.Fill(children, null ); // Initialize the children array to null isEndOfWord = false ; // Initialize the end of word flag to false } public TrieNode[] GetChildren() { return children; } public bool IsEndOfWord() { return isEndOfWord; } public void SetEndOfWord( bool endOfWord) { isEndOfWord = endOfWord; } } // Trie class represents a Trie data structure class Trie { private TrieNode root; public Trie() { root = new TrieNode(); // Initialize the root node } // Insert a word into the Trie public void Insert( string word) { TrieNode current = root; // Start from the root foreach ( char c in word.ToCharArray()) { int index = c - 'a' ; // Calculate the index for the character 'a' to 'z' if (current.GetChildren()[index] == null ) { current.GetChildren()[index] = new TrieNode(); // Create a new node if // it doesn't exist } current = current.GetChildren()[index]; // Move to the child node } current.SetEndOfWord( true ); // Mark the last node as the end of the word } // Search for a word in the Trie public bool Search( string word) { TrieNode current = root; // Start from the root foreach ( char c in word.ToCharArray()) { int index = c - 'a' ; // Calculate the index for the character 'a' to 'z' if (current.GetChildren()[index] == null ) { return false ; // If a character is not found in the Trie, the word is // not present } current = current.GetChildren()[index]; // Move to the child node } return current.IsEndOfWord(); // Check if the last node marks the end of a word } } public class WordSearchIn2DArray { // Count the number of occurrences of a word in a 2D grid of characters public static int CountWordsIn2DArray( string [] grid, string word) { int rows = grid.Length; int cols = grid[0].Length; int count = 0; Trie trie = new Trie(); // Create a Trie data structure trie.Insert(word); // Insert the target word into the Trie // Iterate through the grid to search for the word for ( int i = 0; i < rows; i++) { for ( int j = 0; j < cols; j++) { string current = "" ; // A string to build the current word for ( int k = j; k < cols; k++) { current += grid[i][k]; // Append characters from the grid if (trie.Search(current)) { count++; // If a matching word is found, increment the count } } } } return count; } public static void Main( string [] args) { string [] grid = { "abcde" , "fghij" , "xyabc" , "klmno" }; string word = "abc" ; int result = CountWordsIn2DArray(grid, word); Console.WriteLine(result); // Print the result } } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// TrieNode class represents a node in the Trie data structure class TrieNode { constructor() { this .children = new Array(26).fill( null ); // An array to store references to child nodes this .isEndOfWord = false ; // Indicates if this node marks the end of a word } } // Trie class represents a Trie data structure class Trie { constructor() { this .root = new TrieNode(); // Initialize the root node } // Insert a word into the Trie insert(word) { let current = this .root; // Start from the root for (const c of word) { const index = c.charCodeAt(0) - 'a' .charCodeAt(0); // Calculate the index for the character 'a' to 'z' if (!current.children[index]) { current.children[index] = new TrieNode(); // Create a new node if it doesn't exist } current = current.children[index]; // Move to the child node } current.isEndOfWord = true ; // Mark the last node as the end of the word } // Search for a word in the Trie search(word) { let current = this .root; // Start from the root for (const c of word) { const index = c.charCodeAt(0) - 'a '.charCodeAt(0); // Calculate the index for the character ' a ' to ' z ' if (!current.children[index]) { return false; // If a character is not found in the Trie, the word is not present } current = current.children[index]; // Move to the child node } return current.isEndOfWord; // Check if the last node marks the end of a word } } // Count the number of occurrences of a word in a 2D grid of characters function countWordsIn2DArray(grid, word) { const rows = grid.length; const cols = grid[0].length; let count = 0; const trie = new Trie(); // Create a Trie data structure trie.insert(word); // Insert the target word into the Trie // Iterate through the grid to search for the word for (let i = 0; i < rows; i++) { for (let j = 0; j < cols; j++) { let current = ' '; // A string to build the current word for (let k = j; k < cols; k++) { current += grid[i][k]; // Append characters from the grid if (trie.search(current)) { count++; // If a matching word is found, increment the count } } } } return count; } // Example usage const grid = [ "abcde" , "fghij" , "xyabc" , "klmno" ]; const word = "abc" ; const result = countWordsIn2DArray(grid, word); console.log(result); // Print the result |
2
Time Complexity: O(K + R * C * N), where K is the length of the input word, R is the number of rows, C is the number of columns, and N is the maximum length of the substrings generated from the 2D array.
Auxiliary Space complexity: O(K), where K is the length of the input word