Count the nodes of the tree which make a pangram when concatenated with the sub | Python3 implementation of the approach ; Function that returns if the string x is a pangram ; Function to return the count of nodes which make pangram with the sub - tree nodes ; Function to perform dfs and update the nodes such that weight [ i ] will store the weight [ i ] concatenated with the weights of all the nodes in the sub - tree ; Driver code ; Weights of the nodes ; Edges of the tree
graph = [ [ ] for i in range ( 100 ) ] NEW_LINE weight = [ 0 ] * 100 NEW_LINE def Pangram ( x ) : NEW_LINE INDENT mp = { } NEW_LINE n = len ( x ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT if x [ i ] not in mp : NEW_LINE INDENT mp [ x [ i ] ] = 0 NEW_LINE DEDENT mp [ x [ i ] ] += 1 NEW_LINE DEDENT if ( len ( mp ) == 26 ) : NEW_LINE INDENT return True NEW_LINE DEDENT else : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT def countTotalPangram ( n ) : NEW_LINE INDENT cnt = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( Pangram ( weight [ i ] ) ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT return cnt NEW_LINE DEDENT def dfs ( node , parent ) : NEW_LINE INDENT for to in graph [ node ] : NEW_LINE INDENT if ( to == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( to , node ) NEW_LINE weight [ node ] += weight [ to ] NEW_LINE DEDENT DEDENT n = 6 NEW_LINE weight [ 1 ] = " abcde " NEW_LINE weight [ 2 ] = " fghijkl " NEW_LINE weight [ 3 ] = " abcdefg " NEW_LINE weight [ 4 ] = " mnopqr " NEW_LINE weight [ 5 ] = " stuvwxy " NEW_LINE weight [ 6 ] = " zabcdef " NEW_LINE graph [ 1 ] . append ( 2 ) NEW_LINE graph [ 2 ] . append ( 3 ) NEW_LINE graph [ 2 ] . append ( 4 ) NEW_LINE graph [ 1 ] . append ( 5 ) NEW_LINE graph [ 5 ] . append ( 6 ) NEW_LINE dfs ( 1 , 1 ) NEW_LINE print ( countTotalPangram ( n ) ) NEW_LINE