Split the string into minimum parts such that each part is in the another string | Python3 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
INF = 1e9 + 9 NEW_LINE class TrieNode ( ) : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . child = [ None ] * 26 NEW_LINE DEDENT DEDENT def insert ( idx , s , root ) : NEW_LINE INDENT temp = root NEW_LINE for i in range ( idx , len ( s ) ) : NEW_LINE INDENT if temp . child [ ord ( s [ i ] ) - ord ( ' a ' ) ] == None : NEW_LINE INDENT temp . child [ ord ( s [ i ] ) - ord ( ' a ' ) ] = TrieNode ( ) NEW_LINE DEDENT temp = temp . child [ ord ( s [ i ] ) - ord ( ' a ' ) ] NEW_LINE DEDENT DEDENT def minCuts ( S1 , S2 ) : NEW_LINE INDENT n1 = len ( S1 ) NEW_LINE n2 = len ( S2 ) NEW_LINE root = TrieNode ( ) NEW_LINE for i in range ( n2 ) : NEW_LINE INDENT insert ( i , S2 , root ) NEW_LINE DEDENT dp = [ INF ] * ( n1 + 1 ) NEW_LINE dp [ 0 ] = 0 NEW_LINE for i in range ( n1 ) : NEW_LINE INDENT temp = root NEW_LINE for j in range ( i + 1 , n1 + 1 ) : NEW_LINE INDENT if temp . child [ ord ( S1 [ j - 1 ] ) - ord ( ' a ' ) ] == None : NEW_LINE INDENT break NEW_LINE DEDENT dp [ j ] = min ( dp [ j ] , dp [ i ] + 1 ) NEW_LINE temp = temp . child [ ord ( S1 [ j - 1 ] ) - ord ( ' a ' ) ] NEW_LINE DEDENT DEDENT if dp [ n1 ] >= INF : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return dp [ n1 ] NEW_LINE DEDENT DEDENT S1 = " abcdab " NEW_LINE S2 = " dabc " NEW_LINE print ( minCuts ( S1 , S2 ) ) NEW_LINE