Number of ways to form a given String from the given set of Strings
Given a string str and an array of strings dictionary[], the task is to find the number of ways str can be formed as a concatenation of strings (any number of times) in a dictionary[].
Examples:
Input: str = abab, dictionary[] = { a, b, ab }
Output: 4
Explanation: There are 4 ways to form string str
- a + b + a + b
- ab + a + b
- a + b + ab
- ab + ab
Input: str = Beginner, dictionary[] = { Beginner, for, geek }
Output: 1
Approach: The problem can be solved based on the following idea:
Use Trie data structure to store the strings of a given set in reverse order and count[] where count(i) denotes the number of ways to form string str[0….i]
For every index i, if str[ j…….i ] is found in trie => count(i) += count(j – 1), j: from i to 0
Follow the steps mentioned below to implement the idea:
- Reverse the strings of a given set dictionary[], and insert them into a trie.
- Run loop i: from 0 to N – 1 for count[], where count(i) denotes the number of ways to form string str[0….i].
- Run loop j: from i to 0, conceptually denotes a temporary string str[j….i]
- Correspondingly maintain the pointer ptr which denotes that prefix str[j+1….i] is found in a trie.
- character ch = s[j],
- if( ptr -> children[ch – ‘a’] == nullptr) it means str[j…i] is not found and break the loop.
- if( ptr -> endOfWord == true) count(i) += count(j – 1).
- Return count(n – 1) as an answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; const int alphabet_size = 26; // Trie data structure struct Trie { bool endOfWord = false ; Trie* children[alphabet_size]; Trie() { for ( int i = 0; i < alphabet_size; i++) children[i] = nullptr; } }; // Root of trie Trie* root; // Inserting the strings into trie void insert(string s) { int n = s.size(); Trie* prev = root; for ( int i = 0; i < n; i++) { if (prev->children[s[i] - 'a' ] == nullptr) { Trie* temp = new Trie; prev->children[s[i] - 'a' ] = temp; } prev = prev->children[s[i] - 'a' ]; } prev->endOfWord = true ; } // Function to find number of ways // of forming string str int waysOfFormingString(string& str) { int n = str.size(); // Count[] to store the answer // of prefix string str[0....i] vector< int > count(n, 0); for ( int i = 0; i < n; i++) { Trie* ptr = root; for ( int j = i; j >= 0; j--) { char ch = str[j]; // If not found, break // out from loop if (ptr->children[ch - 'a' ] == nullptr) break ; ptr = ptr->children[ch - 'a' ]; // String found, update the // count(i) if (ptr->endOfWord == true ) count[i] += j > 0 ? count[j - 1] : 1; } } return count[n - 1]; } // Driver code int main() { string str = "abab" ; string dictionary[] = { "a" , "b" , "ab" }; int m = 3; root = new Trie; // Construct trie for ( int i = 0; i < m; i++) { reverse(dictionary[i].begin(), dictionary[i].end()); insert(dictionary[i]); } // Function call cout << waysOfFormingString(str) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; // Trie data structure class TrieNode { public boolean endOfWord = false ; public TrieNode[] children = new TrieNode[ 26 ]; } class Trie { // Root of trie private TrieNode root = new TrieNode(); // Insert a string into the trie public void insert(String s) { TrieNode prev = root; for ( char c : s.toCharArray()) { int index = c - 'a' ; if (prev.children[index] == null ) { prev.children[index] = new TrieNode(); } prev = prev.children[index]; } prev.endOfWord = true ; } // Find the number of ways to form the given string // using the strings in the trie public int waysOfFormingString(String str) { int n = str.length(); int [] count = new int [n]; // For each index i in the input string for ( int i = 0 ; i < n; i++) { TrieNode ptr = root; // Check all possible substrings of str ending // at index i for ( int j = i; j >= 0 ; j--) { char ch = str.charAt(j); int index = ch - 'a' ; if (ptr.children[index] == null ) { break ; } ptr = ptr.children[index]; if (ptr.endOfWord) { // If the substring ending at index j is // in the trie, update the count count[i] += j > 0 ? count[j - 1 ] : 1 ; } } } // The final count is the number of ways to form the // entire string return count[n - 1 ]; } } class GFG { public static void main(String[] args) { String str = "abab" ; String[] dictionary = { "a" , "b" , "ab" }; int m = dictionary.length; Trie trie = new Trie(); // Insert the reversed strings into the trie for (String s : dictionary) { char [] arr = s.toCharArray(); StringBuilder sb = new StringBuilder( new String(arr)); trie.insert(sb.reverse().toString()); } // Find the number of ways to form the input string // using the strings in the trie System.out.println(trie.waysOfFormingString(str)); } } // This code is contributed by sankar. |
Python3
# Trie data structure class Trie: def __init__( self ): self .endOfWord = False self .children = [ None ] * 26 # Inserting the strings into trie def insert(root, s): n = len (s) prev = root for i in range (n): index = ord (s[i]) - ord ( 'a' ) if prev.children[index] is None : prev.children[index] = Trie() prev = prev.children[index] prev.endOfWord = True # Function to find number of ways # of forming string str def waysOfFormingString(root, s): n = len (s) # Count[] to store the answer # of prefix string str[0....i] count = [ 0 ] * n for i in range (n): ptr = root for j in range (i, - 1 , - 1 ): ch = s[j] # If not found, break # out from loop index = ord (ch) - ord ( 'a' ) if ptr.children[index] is None : break ptr = ptr.children[index] # String found, update the # count(i) if ptr.endOfWord: if j > 0 : count[i] + = count[j - 1 ] else : count[i] + = 1 return count[n - 1 ] # Driver code if __name__ = = '__main__' : str = "abab" dictionary = [ "a" , "b" , "ab" ] m = 3 root = Trie() # Construct trie for i in range (m): insert(root, dictionary[i][:: - 1 ]) # Function call print (waysOfFormingString(root, str )) |
C#
using System; public class TrieNode { public bool endOfWord = false ; public TrieNode[] children = new TrieNode[26]; } public class Trie { private TrieNode root = new TrieNode(); // Insert a string into the trie public void Insert( string s) { TrieNode prev = root; foreach ( char c in s) { int index = c - 'a' ; if (prev.children[index] == null ) prev.children[index] = new TrieNode(); prev = prev.children[index]; } prev.endOfWord = true ; } // Find the number of ways to form the given string // using the strings in the trie public int WaysOfFormingString( string str) { int n = str.Length; int [] count = new int [n]; // For each index i in the input string for ( int i = 0; i < n; i++) { TrieNode ptr = root; // Check all possible substrings of str ending // at index i for ( int j = i; j >= 0; j--) { char ch = str[j]; int index = ch - 'a' ; if (ptr.children[index] == null ) break ; ptr = ptr.children[index]; if (ptr.endOfWord) // If the substring ending at index j is // in the trie, update the count count[i] += j > 0 ? count[j - 1] : 1; } } // The final count is the number of ways to form the // entire string return count[n - 1]; } } public class Program { public static void Main() { string str = "abab" ; string [] dictionary = { "a" , "b" , "ab" }; int m = dictionary.Length; Trie trie = new Trie(); // Insert the reversed strings into the trie foreach ( string s in dictionary) { char [] arr = s.ToCharArray(); Array.Reverse(arr); trie.Insert( new string (arr)); } // Find the number of ways to form the input string // using the strings in the trie Console.WriteLine(trie.WaysOfFormingString(str)); } } // This code is contributed by lokeshpotta20. |
Javascript
//Javascript code const alphabet_size = 26; class Trie { constructor() { this .endOfWord = false ; this .children = Array(alphabet_size).fill( null ); } } let root; function insert(s) { let n = s.length; let prev = root; for (let i = 0; i < n; i++) { if (prev.children[s[i].charCodeAt() - 'a' .charCodeAt()] === null ) { let temp = new Trie(); prev.children[s[i].charCodeAt() - 'a' .charCodeAt()] = temp; } prev = prev.children[s[i].charCodeAt() - 'a' .charCodeAt()]; } prev.endOfWord = true ; } function waysOfFormingString(str) { let n = str.length; let count = Array(n).fill(0); for (let i = 0; i < n; i++) { let ptr = root; for (let j = i; j >= 0; j--) { let ch = str[j]; if (ptr.children[ch.charCodeAt() - 'a' .charCodeAt()] === null ) break ; ptr = ptr.children[ch.charCodeAt() - 'a' .charCodeAt()]; if (ptr.endOfWord === true ) count[i] += j > 0 ? count[j - 1] : 1; } } return count[n - 1]; } //Driver code function main() { let str = "abab" ; let dictionary = [ "a" , "b" , "ab" ]; let m = 3; root = new Trie(); // Construct trie for (let i = 0; i < m; i++) { dictionary[i] = dictionary[i].split( "" ).reverse().join( "" ); insert(dictionary[i]); } //functiom call console.log(waysOfFormingString(str)); } main(); //This code is contributed by NarasingaNikhil |
4
Time Complexity: O(N * N)
Auxiliary Space: O(M)
Another Approach: The problem can be solved based on the following idea:
Using polynomial hashing, the hash value of any substring of a string str can be calculated in O(1) time after an O(n) time preprocessing.
The fact that there are at most O(?m) distinct string lengths if total length of all strings in dictionary[] is m.
count[] where count(i) denotes the number of ways to form string str[0….i]
For every index i,
if str[ j…….i ] is found in diciionary[] => count(i) += count(j – 1), j: from i to 0
Follow the steps mentioned below to implement the idea:
- https://www.w3wiki.net/string-hashing-using-polynomial-rolling-hash-function/
- Construct a map of set hash_grp that contains all hash values of the strings in the dictionary[] grouped according to the string’s length.
- Construct an array hashed_arr[] that stores the hashed values of all prefixes of string str.
- When calculating a value of count(i), we go through all values of len such that there is a string of length len in the dictionary[].
- calculate the hash value of s[i ? len +1………i] and check if it belongs to hashed_grp[len].
- hashed_arr[j……..i] * pj = hashed_arr[0……i] – hashed_arr[0……j – 1], where p is an arbitrary constant integer.
- count(i) += count(j – 1).
- Return count(n – 1) as an answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; long long p = 31, m = 1e9 + 7; //x riased to y int power( int x, int y, int mod) { int res = 1; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = (res * x)%mod; // y = y/2 y = y >> 1; // Change x to x^2 x = (x * x)%mod; } return res % mod; } //getting the hash value of string s int get_hash(string &s) { long long hash = 0; long long p_pow = 1; int n = s.size(); for ( int i = 0; i < n; i++) { hash = ((hash + (s[i] - 'a' + 1) * p_pow) % m); p_pow = (p_pow * p) % m; } return hash; } //constructing hash values of all prefix // of string s vector< int > hashing(string &s) { int n = s.size(); vector< int > hash(n, 0); hash[0] = s[0] - 'a' + 1; long long p_pow = p; for ( int i = 1; i < n; i++) { hash[i] = ( int )((hash[i - 1] + (s[i] - 'a' + 1) * p_pow) % m); p_pow = (p_pow * p) % m; } return hash; } // Function to find number of ways // of forming string str int waysOfFormingString(string s, vector<string> &dic) { int n = s.size(); int k = dic.size(); // map (length, hash_values) map< int , set< int >> hash_grp; //hash values for all strings for ( int i = 0; i < k; i++) { int p = get_hash(dic[i]); hash_grp[dic[i].size()].insert(p); } // hashed array for prefix of str vector< int > hashed_arr = hashing(s); // required answer for prefixes of str vector< int > count(n, 0); for ( int i = 0; i < n; i++) { // traversing every lengths of strings // in dictionary[] for ( auto x : hash_grp) { int len = x.first; if (i + 1 < len) break ; //calculating hash[j....i] int p_pow = power(p, i - len + 1, m); int hashed_value = (i+1 != len) ? ((hashed_arr[i] - hashed_arr[i - len]) / p_pow) : (hashed_arr[i] / p_pow); // whether hash value of string of length len //exist in an array of strings if ((x.second).find(hashed_value) != (x.second).end()) count[i] += (i + 1 != len) ? count[i - len] : 1; } } //return answer return count[n - 1]; } // Driver program to test above functions int main() { // given string str string str = "abab" ; //set of strings vector<string> dictionary = { "a" , "b" , "ab" }; cout << waysOfFormingString(str, dictionary) << endl; return 0; } |
Java
import java.util.*; public class WaysOfFormingString { static long p = 31 , m = 1000000007 ; // Function to calculate x raised to y modulo mod static long power( long x, long y, long mod) { long res = 1 ; while (y > 0 ) { if ((y & 1 ) == 1 ) { res = (res * x) % mod; } x = (x * x) % mod; y >>= 1 ; } return res; } // Function to calculate hash value of a string static long getHash(String s) { long hash = 0 , pPow = 1 ; for ( int i = 0 ; i < s.length(); i++) { hash = (hash + (s.charAt(i) - 'a' + 1 ) * pPow) % m; pPow = (pPow * p) % m; } return hash; } // Function to construct array of hash values of prefixes of a string static List<Long> hashing(String s) { int n = s.length(); List<Long> hash = new ArrayList<>(n); hash.add(( long )(s.charAt( 0 ) - 'a' + 1 )); long pPow = p; for ( int i = 1 ; i < n; i++) { hash.add((hash.get(i - 1 ) + (s.charAt(i) - 'a' + 1 ) * pPow) % m); pPow = (pPow * p) % m; } return hash; } // Function to count number of ways of forming a string using given dictionary static int waysOfFormingString(String s, List<String> dict) { int n = s.length(), k = dict.size(); // map to store hash values of strings in dictionary according to their lengths Map<Integer, Set<Long>> hashGrp = new HashMap<>(); for (String word : dict) { long p = getHash(word); hashGrp.computeIfAbsent(word.length(), k1 -> new HashSet<>()).add(p); } // array to store hash values of prefixes of the given string List<Long> hashedArr = hashing(s); // array to store number of ways of forming prefixes of the given string int [] count = new int [n]; for ( int i = 0 ; i < n; i++) { for (Map.Entry<Integer, Set<Long>> entry : hashGrp.entrySet()) { int len = entry.getKey(); if (i + 1 < len) { break ; } long pPow = power(p, i - len + 1 , m); long hashedValue = (i + 1 != len) ? ((hashedArr.get(i) - hashedArr.get(i - len)) / pPow) : (hashedArr.get(i) / pPow); if (entry.getValue().contains(hashedValue)) { count[i] += (i + 1 != len) ? count[i - len] : 1 ; } } } return count[n - 1 ]; } public static void main(String[] args) { String str = "abab" ; List<String> dictionary = Arrays.asList( "a" , "b" , "ab" ); System.out.println(waysOfFormingString(str, dictionary)); } } |
Python3
# Python code to implement the approach # Values for hashing p = 31 m = 10 * * 9 + 7 # x riased to y def power(x, y, mod): res = 1 while y > 0 : # If y is odd, multiply x with result if y % 2 = = 1 : res = (res * x) % mod # y = y/2 y = y / / 2 # Change x to x^2 x = (x * x) % mod return res % mod # getting the hash value of string s def get_hash(s): hash = 0 p_pow = 1 n = len (s) for i in range (n): hash = ( hash + ( ord (s[i]) - ord ( 'a' ) + 1 ) * p_pow) % m p_pow = (p_pow * p) % m return hash # constructing hash values of all prefix # of string s def hashing(s): n = len (s) hash = [ 0 ] * n hash [ 0 ] = ord (s[ 0 ]) - ord ( 'a' ) + 1 p_pow = p for i in range ( 1 , n): hash [i] = ( hash [i - 1 ] + ( ord (s[i]) - ord ( 'a' ) + 1 ) * p_pow) % m p_pow = (p_pow * p) % m return hash # Function to find number of ways # of forming string str def waysOfFormingString(s, dic): n = len (s) k = len (dic) # Dictionary to store (length, hash_values) hash_grp = {} # Hash values for all strings for word in dic: h = get_hash(word) hash_grp.setdefault( len (word), set ()).add(h) # Hashed array for prefix of str hashed_arr = hashing(s) # Required answer for prefixes of str count = [ 0 ] * n for i in range (n): # traversing every lengths of strings # in dictionary[] for length, hash_set in hash_grp.items(): if i + 1 < length: break p_pow = power(p, i - length + 1 , m) hashed_value = (hashed_arr[i] - hashed_arr[i - length]) / / p_pow if i + 1 ! = length else hashed_arr[i] / / p_pow # whether hash value of string of length len # exist in an array of strings if hashed_value in hash_set: count[i] + = count[i - length] if i + 1 ! = length else 1 # Return answer return count[n - 1 ] # Driver program to test above functions if __name__ = = "__main__" : # given string str str = "abab" # set of strings dictionary = [ "a" , "b" , "ab" ] print (waysOfFormingString( str , dictionary)) # This code is contributed by Pushpesh raj |
C#
// C# code to implement the approach using System; using System.Collections.Generic; namespace ConsoleApp { class Gfg { static long p = 31, m = 1000000007; //x riased to y static int power( int x, int y, int mod) { int res = 1; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) res = ( int )((res * ( long )x) % mod); // y = y/2 y = y >> 1; // Change x to x^2 x = ( int )((x * ( long )x) % mod); } return res % mod; } //getting the hash value of string s static int get_hash( string s) { long hash = 0; long p_pow = 1; int n = s.Length; for ( int i = 0; i < n; i++) { hash = ((hash + (s[i] - 'a' + 1) * p_pow) % m); p_pow = (p_pow * p) % m; } return ( int )hash; } //constructing hash values of all prefix // of string s static List< int > hashing( string s) { int n = s.Length; List< int > hash = new List< int >(n); hash.Add(s[0] - 'a' + 1); long p_pow = p; for ( int i = 1; i < n; i++) { hash.Add(( int )((hash[i - 1] + (s[i] - 'a' + 1) * p_pow) % m)); p_pow = (p_pow * p) % m; } return hash; } // Function to find number of ways // of forming string str static int waysOfFormingString( string s, List< string > dic) { int n = s.Length; int k = dic.Count; // map (length, hash_values) Dictionary< int , HashSet< int >> hashGrp = new Dictionary< int , HashSet< int >>(); //hash values for all strings for ( int i = 0; i < k; i++) { int p = get_hash(dic[i]); if (!hashGrp.ContainsKey(dic[i].Length)) hashGrp[dic[i].Length] = new HashSet< int >(); hashGrp[dic[i].Length].Add(p); } // hashed array for prefix of str List< int > hashedArr = hashing(s); // required answer for prefixes of str List< int > count = new List< int >( new int [n]); for ( int i = 0; i < n; i++) { // traversing every lengths of strings // in dictionary[] foreach (KeyValuePair< int , HashSet< int >> x in hashGrp) { int len = x.Key; if (i + 1 < len) break ; //calculating hash[j....i] int p_pow = power(( int )p, i - len + 1, ( int )m); int hashedValue = (i + 1 != len) ? ((hashedArr[i] - hashedArr[i - len]) / p_pow) : (hashedArr[i] / p_pow); // whether hash value of string of length len //exist in an array of strings if (x.Value.Contains(hashedValue)) count[i] += (i + 1 != len) ? count[i - len] : 1; } } //return answer return count[n - 1]; } // Driver program to test above functions static void Main( string [] args) { // given string str string str = "abab" ; //set of strings List< string > dictionary = new List< string > { "a" , "b" , "ab" }; Console.WriteLine(waysOfFormingString(str, dictionary)); } } } |
Javascript
//x riased to y function power(x, y, mod) { let res = 1; while (y > 0) { // If y is odd, multiply x with result if (y % 2 == 1) { res = (res * x) % mod; } // y = y/2 y = Math.floor(y / 2); // Change x to x^2 x = (x * x) % mod; } return res % mod; } //getting the hash value of string s function getHash(s) { const p = 31; const m = 1000000007; let hash = 0; let pPow = 1; const n = s.length; for (let i = 0; i < n; i++) { hash = ((hash + (s.charCodeAt(i) - 'a' .charCodeAt(0) + 1) * pPow) % m); pPow = (pPow * p) % m; } return hash; } //constructing hash values of all prefix // of string s function hashing(s) { const p = 31; const m = 1000000007; const n = s.length; const hash = new Array(n); hash[0] = s.charCodeAt(0) - 'a' .charCodeAt(0) + 1; let pPow = p; for (let i = 1; i < n; i++) { hash[i] = ((hash[i - 1] + (s.charCodeAt(i) - 'a' .charCodeAt(0) + 1) * pPow) % m); pPow = (pPow * p) % m; } return hash; } // Function to find number of ways // of forming string str function waysOfFormingString(s, dic) { const p = 31; const m = 1000000007; const n = s.length; const k = dic.length; // map (length, hash_values) const hashGrp = new Map(); //hash values for all strings for (let i = 0; i < k; i++) { const p = getHash(dic[i]); if (!hashGrp.has(dic[i].length)) { hashGrp.set(dic[i].length, new Set()); } hashGrp.get(dic[i].length).add(p); } // hashed array for prefix of str const hashedArr = hashing(s); // required answer for prefixes of str const count = new Array(n).fill(0); for (let i = 0; i < n; i++) { // traversing every lengths of strings // in dictionary[] for (const [len, hashValues] of hashGrp) { if (i + 1 < len) { break ; } //calculating hash[j....i] const pPow = power(p, i - len + 1, m); const hashedValue = (i + 1 != len) ? ((hashedArr[i] - hashedArr[i - len]) / pPow) : (hashedArr[i] / pPow); // whether hash value of string of length len //exist in an array of strings if (hashValues.has(hashedValue)) { count[i] += (i + 1 != len) ? count[i - len] : 1; } } } //return answer return count[n - 1]; } // Driver code to test above functions // Given string const str = "abab" ; //set of strings const dictionary = [ "a" , "b" , "ab" ]; console.log(waysOfFormingString(str, dictionary)); |
4
Time Complexity: O(N * ?M)
Auxiliary Space: O(N + ?M)
M is the total length of all strings in a set and N is the length of a given string.