Split the string into minimum parts such that each part is in the another string | Javascript 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
let INF = ( 1e9 + 9 ) ; class Node { constructor ( ) { } } function TrieNode ( ) { let temp = new Node ( ) ; temp . child = new Node ( 26 ) ; for ( let i = 0 ; i < 26 ; i ++ ) { temp . child [ i ] = null ; } return temp ; } function insert ( idx , s , root ) { let temp = root ; for ( let i = idx ; i < s . length ; i ++ ) { if ( temp . child [ s [ i ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] == null ) temp . child [ s [ i ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] = new TrieNode ( ) ; temp = temp . child [ s [ i ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] ; } } function minCuts ( S1 , S2 ) { let n1 = S1 . length ; let n2 = S2 . length ; let root = new TrieNode ( ) ; for ( let i = 0 ; i < n2 ; i ++ ) { insert ( i , S2 , root ) ; } let dp = new Array ( n1 + 1 ) ; dp . fill ( INF ) ; dp [ 0 ] = 0 ; for ( let i = 0 ; i < n1 ; i ++ ) { let temp = root ; for ( let j = i + 1 ; j <= n1 ; j ++ ) { if ( temp . child [ S1 [ j - 1 ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] == null ) break ; dp [ j ] = Math . min ( dp [ j ] , dp [ i ] + 1 ) ; temp = temp . child [ S1 [ j - 1 ] . charCodeAt ( ) - ' ' . charCodeAt ( ) ] ; } } if ( dp [ n1 ] >= INF ) return - 1 ; else return dp [ n1 ] ; } let S1 = " " ; let S2 = " " ; document . write ( minCuts ( S1 , S2 ) ) ;