text: Split the string into minimum parts such that each part is in the another string | C ++ implementation to split the string into minimum number of parts such that each part is also present in the another string ; Node of Trie ; Function to insert a node in the Trie Data Structure ; Inserting every character from idx till end to string into trie ; if there is no edge corresponding to the ith character , then make a new node ; Function to find the minimum number of parts such that each part is present into another string ; Making a new trie ; Inserting every substring of S2 in trie ; Creating dp array and init it with infinity ; Base Case ; Starting the cut from ith character taking temporary node pointer for checking whether the substring [ i , j ) is present in trie of not ; if the jth character is not in trie we 'll break ; Updating the the ending of jth character with dp [ i ] + 1 ; Descending the trie pointer ; Answer not possible ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int INF = 1e9 + 9 ; struct TrieNode { TrieNode * child [ 26 ] = { NULL } ; } ; void insert ( int idx , string & s , TrieNode * root ) { TrieNode * temp = root ; for ( int i = idx ; i < s . length ( ) ; i ++ ) { if ( temp -> child [ s [ i ] - ' a ' ] == NULL ) temp -> child [ s [ i ] - ' a ' ] = new TrieNode ; temp = temp -> child [ s [ i ] - ' a ' ] ; } } int minCuts ( string S1 , string S2 ) { int n1 = S1 . length ( ) ; int n2 = S2 . length ( ) ; TrieNode * root = new TrieNode ; for ( int i = 0 ; i < n2 ; i ++ ) { insert ( i , S2 , root ) ; } vector < int > dp ( n1 + 1 , INF ) ; dp [ 0 ] = 0 ; for ( int i = 0 ; i < n1 ; i ++ ) { TrieNode * temp = root ; for ( int j = i + 1 ; j <= n1 ; j ++ ) { if ( temp -> child [ S1 [ j - 1 ] - ' a ' ] == NULL ) break ; dp [ j ] = min ( dp [ j ] , dp [ i ] + 1 ) ; temp = temp -> child [ S1 [ j - 1 ] - ' a ' ] ; } } if ( dp [ n1 ] >= INF ) return -1 ; else return dp [ n1 ] ; } int main ( ) { string S1 = " abcdab " ; string S2 = " dabc " ; cout << minCuts ( S1 , S2 ) ; }