Split the string into minimum parts such that each part is in the another string | Java 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
import java . util . * ; class GFG { static int INF = ( int ) ( 1e9 + 9 ) ; static class TrieNode { TrieNode [ ] child = new TrieNode [ 26 ] ; } ; static void insert ( int idx , String s , TrieNode root ) { TrieNode temp = root ; for ( int i = idx ; i < s . length ( ) ; i ++ ) { if ( temp . child [ s . charAt ( i ) - ' a ' ] == null ) temp . child [ s . charAt ( i ) - ' a ' ] = new TrieNode ( ) ; temp = temp . child [ s . charAt ( i ) - ' a ' ] ; } } static 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 ) ; } int [ ] dp = new int [ n1 + 1 ] ; Arrays . fill ( dp , 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 . charAt ( j - 1 ) - ' a ' ] == null ) break ; dp [ j ] = Math . min ( dp [ j ] , dp [ i ] + 1 ) ; temp = temp . child [ S1 . charAt ( j - 1 ) - ' a ' ] ; } } if ( dp [ n1 ] >= INF ) return - 1 ; else return dp [ n1 ] ; } public static void main ( String [ ] args ) { String S1 = " abcdab " ; String S2 = " dabc " ; System . out . print ( minCuts ( S1 , S2 ) ) ; } }