Find all concatenations of words in Array
Given an array of strings arr[] (1 <= |arr[i]| <= 20) of size N (1 <= N <= 104), the task is to find all strings from the given array that are formed by the concatenation of strings in the same given array.
Examples:
Input: arr[]= { “geek”, “Beginner”, “for”, “w3wiki”, “g”, “f”, “g”, “gfg” };
Output: “w3wiki”Input: arr[] = {“g”, “gforg”, “for”}
Output: {“gforg”}
Naive Approach: The basic way to solve the problem is as follows:
Generate all possible concatation of strings and check if it exists in given array or not. As there are two options for each string of array that wheather we concatenate it or not. Finally, after exploring all such options we’re able to generate all possible concatenations.
Complexity Analysis:
- Time Complexity: 2n
- Auxiliary Space: n
Find all concatenations of words in an array using Hashmap and Recursion:
The idea is to use a map to keep track of word occurrences. For each string extract its prefix, suffix and Check if both the prefix and suffix are in the map (can be concatenated) or Check if the prefix is in the map and recursively check the suffix
Step-by-step approach:
- Store each word in the map for checking the string is present in given array string or not.
- Create an array of string result to store the resulting concatenated strings
- Iterate through the strings and check if they can be concatenated
- Create a Helper function isConcat() to determine if a word can be concatenated
- Check if both the prefix and suffix of string are in the map (can be concatenated), return true
- Check if the prefix is in the map and recursively check the suffix, return true
- If no valid concatenation is found, return false
- Create a Helper function isConcat() to determine if a word can be concatenated
- Count the frequency of each word and store it in the map
Below is the implemenation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Create an unordered map to store the // frequency of words in the input list unordered_map<string, int > unmap; // Helper function to determine if a word // can be concatenated bool isConcat( int i, string& word) { // Initialize a prefix to build the // word incrementally string prefix = ""; for ( int k = 0; k < word.size() - 1; k++) { // Add characters to the prefix prefix += word[k]; // Extract the remaining part of the // word as the suffix string suffix = word.substr(k + 1); // Check if both the prefix and suffix // are in the map (can be concatenated) if (unmap.find(prefix) != unmap.end() && unmap.find(suffix) != unmap.end()) { return true ; } // Check if the prefix is in the map // and recursively check the suffix else if (unmap.find(prefix) != unmap.end() && isConcat(i + 1, suffix)) { return true ; } } // If no valid concatenation is found, // return false return false ; } // Drivers code int main() { vector<string> arr = { "geek", "Beginner", " for ", "w3wiki", "g", "f", "g", "gfg" }; // Create a vector to store the resulting // concatenated words vector<string> result; // Count the frequency of each word and // store it in the map for ( auto s : arr) unmap[s]++; // Iterate through the words and check if // they can be concatenated for ( auto s : arr) { // If the word can be concatenated, // add it to the result if (isConcat(0, s)) result.push_back(s); } // Print result for ( auto s : result) cout << s << " "; } |
Java
import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class ConcatenatedWords { // Create a map to store the frequency of words in the // input list static Map<String, Integer> wordFrequency = new HashMap<>(); // Helper function to determine if a word can be // concatenated public static boolean isConcat(String word) { // Initialize a prefix to build the word // incrementally StringBuilder prefix = new StringBuilder(); for ( int k = 0 ; k < word.length() - 1 ; k++) { // Add characters to the prefix prefix.append(word.charAt(k)); // Extract the remaining part of the word as the // suffix String suffix = word.substring(k + 1 ); // Check if both the prefix and suffix are in // the map (can be concatenated) if (wordFrequency.containsKey(prefix.toString()) && wordFrequency.containsKey(suffix)) { return true ; } // Check if the prefix is in the map and // recursively check the suffix if (wordFrequency.containsKey(prefix.toString()) && isConcat(suffix)) { return true ; } } // If no valid concatenation is found, return false return false ; } public static void main(String[] args) { List<String> words = new ArrayList<>(); words.add( "geek" ); words.add( "Beginner" ); words.add( "for" ); words.add( "w3wiki" ); words.add( "g" ); words.add( "f" ); words.add( "g" ); words.add( "gfg" ); // Create a list to store the resulting concatenated // words List<String> result = new ArrayList<>(); // Count the frequency of each word and store it in // the map for (String word : words) { wordFrequency.put( word, wordFrequency.getOrDefault(word, 0 ) + 1 ); } // Iterate through the words and check if they can // be concatenated for (String word : words) { // If the word can be concatenated, add it to // the result if (isConcat(word)) { result.add(word); } } // Print result for (String word : result) { System.out.print(word + " " ); } } } |
Python
# code by flutterfly # Create a dictionary to store the # frequency of words in the input list unmap = {} # Helper function to determine if a word # can be concatenated def is_concat(i, word): global unmap # Initialize a prefix to build the # word incrementally prefix = "" for k in range ( len (word) - 1 ): # Add characters to the prefix prefix + = word[k] # Extract the remaining part of the # word as the suffix suffix = word[k + 1 :] # Check if both the prefix and suffix # are in the dictionary (can be concatenated) if prefix in unmap and suffix in unmap: return True # Check if the prefix is in the dictionary # and recursively check the suffix elif prefix in unmap and is_concat(i + 1 , suffix): return True # If no valid concatenation is found, # return False return False # Drivers code if __name__ = = "__main__" : arr = [ "geek" , "Beginner" , "for" , "w3wiki" , "g" , "f" , "g" , "gfg" ] # Create a list to store the resulting # concatenated words result = [] # Count the frequency of each word and # store it in the dictionary for s in arr: if s in unmap: unmap[s] + = 1 else : unmap[s] = 1 # Iterate through the words and check if # they can be concatenated for s in arr: # If the word can be concatenated, # add it to the result if is_concat( 0 , s): result.append(s) # Print result print ( " " .join(result)) |
C#
//code by Flutterfly using System; using System.Collections.Generic; class GFG { // Create a dictionary to store the frequency of words in the input list static Dictionary< string , int > unmap = new Dictionary< string , int >(); // Helper function to determine if a word can be concatenated static bool IsConcat( int i, string word) { // Initialize a prefix to build the word incrementally string prefix = "" ; for ( int k = 0; k < word.Length - 1; k++) { // Add characters to the prefix prefix += word[k]; // Extract the remaining part of the word as the suffix string suffix = word.Substring(k + 1); // Check if both the prefix and suffix are in the dictionary (can be concatenated) if (unmap.ContainsKey(prefix) && unmap.ContainsKey(suffix)) { return true ; } // Check if the prefix is in the dictionary and recursively check the suffix else if (unmap.ContainsKey(prefix) && IsConcat(i + 1, suffix)) { return true ; } } // If no valid concatenation is found, return false return false ; } // Drivers code static void Main() { string [] arr = { "geek" , "Beginner" , "for" , "w3wiki" , "g" , "f" , "g" , "gfg" }; // Create a list to store the resulting concatenated words List< string > result = new List< string >(); // Count the frequency of each word and store it in the dictionary foreach ( string s in arr) { if (unmap.ContainsKey(s)) { unmap[s]++; } else { unmap[s] = 1; } } // Iterate through the words and check if they can be concatenated foreach ( string s in arr) { // If the word can be concatenated, add it to the result if (IsConcat(0, s)) { result.Add(s); } } // Print result Console.WriteLine( string .Join( " " , result)); } } |
Javascript
// Create an object to store the frequency of words in the input list let unmap = {}; // Helper function to determine if a word can be concatenated function isConcat(i, word) { // Initialize a prefix to build the word incrementally let prefix = "" ; for (let k = 0; k < word.length - 1; k++) { // Add characters to the prefix prefix += word[k]; // Extract the remaining part of the word as the suffix let suffix = word.substring(k + 1); // Check if both the prefix and suffix are in the object (can be concatenated) if (unmap.hasOwnProperty(prefix) && unmap.hasOwnProperty(suffix)) { return true ; } // Check if the prefix is in the object and recursively check the suffix else if (unmap.hasOwnProperty(prefix) && isConcat(i + 1, suffix)) { return true ; } } // If no valid concatenation is found, return false return false ; } // Drivers code let arr = [ "geek" , "Beginner" , "for" , "w3wiki" , "g" , "f" , "g" , "gfg" ]; // Create an array to store the resulting concatenated words let result = []; // Count the frequency of each word and store it in the object arr.forEach(s => { unmap[s] = (unmap[s] || 0) + 1; }); // Iterate through the words and check if they can be concatenated arr.forEach(s => { // If the word can be concatenated, add it to the result if (isConcat(0, s)) { result.push(s); } }); // Print result console.log(result.join( " " )); |
w3wiki gfg
Time Complexity: O(N * L^2), where N is the number of words and L is the maximum word length.
Auxiliary Space: O(N)
Contact Us