Sum of all LCP of maximum length by selecting any two Strings at a time | Javascript program to find Sum of all LCP of maximum length by selecting any two Strings at a time ; Initially visited value for all nodes is zero ; Counts the number of times the node is visited while making the trie ; Using map to store the pointers of children nodes for dynamic implementation , for making the program space efiicient ; Head node of the trie is initialize as ' \0' , after this all Strings add ; Function to insert the Strings in the trie ; Inserting character - by - character ; If the node of ch is not present in map make a new node and add in map ; Recursive function to calculate the answer argument is passed by reference ; To store changed visited values from children of this node i . e . number of nodes visited by its children ; Updating the visited variable , telling number of nodes that have already been visited by its children ; If node . visited > 1 , means more than one String has prefix up till this node common in them ; Number of String pair with current node common in them ; Updating visited variable of current node ; Returning the total number of nodes already visited that needs to be updated to previous node ; Function to run the dfs function for the first time and give the answer variable ; Stores the final answer as sum of all depths ; Driver code
class TrieNode { constructor ( x ) { this . val = x ; this . visited = 0 ; this . children = new Map ( ) ; } } class Trie { constructor ( ) { this . head = new TrieNode ( ' \0 ' ) ; this . ans = 0 ; } addWord ( s ) { let temp = this . head ; let n = s . length ; for ( let i = 0 ; i < n ; i ++ ) { let ch = s [ i ] ; if ( temp . children . get ( ch ) == null ) { temp . children . set ( ch , new TrieNode ( ch ) ) ; } temp = temp . children . get ( ch ) ; temp . visited ++ ; } } dfs ( node , depth ) { let vis = 0 ; for ( let [ key , value ] of node . children . entries ( ) ) { vis += this . dfs ( value , depth + 1 ) ; } node . visited -= vis ; let String_pair = 0 ; if ( node . visited > 1 ) { String_pair = ( node . visited / 2 ) ; this . ans += ( depth * String_pair ) ; node . visited -= ( 2 * String_pair ) ; } return ( 2 * String_pair + vis ) ; } dfshelper ( ) { this . ans = 0 ; this . dfs ( this . head , 0 ) ; return this . ans ; } } let T = new Trie ( ) ; let str = [ " " , " " , " " , " " , " " , " " ] ; let n = 6 ; for ( let i = 0 ; i < n ; i ++ ) { T . addWord ( str [ i ] ) ; } let ans = T . dfshelper ( ) ; document . write ( ans ) ;