Java | Trie | Detailed Explanation and Comments
Here I will explain the super detailed thought process to solve this problem. For a concise explanation, only read section Problem Approach and Final Approach I
Here I will explain the super detailed thought process to solve this problem. For a concise explanation, only read section **Problem Approach** and **Final Approach Implementation**.\n\n**Problem Approach:**\nFor each String **S** in words, for all **S\'s prefixes Sj** (**j denoting the length of Sj**), we essentially want to **sum up** the **number of strings in words that start with Sj**.\n\n**First Thought:**\n\n***Brute force***\nRecord Sjn for any String S in words. Say words = ["abc", "ab", "b", "bc", "ccc"], we record Sjn for "a" (2), "ab" (2), "abc" (1), "b" (2), "bc" (1), "c" (1), "cc" (1), "ccc" (1). \n\n***Implementation***\nFor each S, we increment each Sjn by 1. Then for each S, the answer is the sum of Sjn.\n\n***Issue: O(n ^ 3) TLE***\n**Say there are 1000 strings, each with 1000 characters, and the first 3 characters of each S are distinct** (say if one String starts with "abc", others cannot. It\'s possible since there are 26^3 > 1000 combinations of the first 3 characters), note that any prefix Sj for any S s.t. j >= 3 are distinct (for 2 prefixes P1 and P2 that belong to the same S, they are different, otherwise, they differ by the first 3 characters, thus P1 and P2 must also be different), resulting in the number of characters for all distinct Sj to be the magnitude of **1000 (distinct S) * ((3 + 1000) * 998 / 2) (number of characters in all Sj for S) = O(n ^ 3)** where n = 1000, resulting in TLE (usually the most you can get to pass is 10^7).\n\n***Solution***\nWe notice there are many overlaps between prefixes of the same S, say S999 and S1000, the first 999 characters are the same. So instead of making each Sj separate strings, we might be able to compact the representing of Sj into something that has O(n) space / time complexity. We use Trie to achieve this.\n\nIf you don\'t know Trie, here\'s a 5-min tutorial.\nhttps://www.youtube.com/watch?v=zIjfhVPRZCg\n\n**Final Approach:**\nUse Trie, each S is a path in the Trie from the root of Trie. Think of the path for S as a linked-list of Trie nodes with head = root, where the i-th node in the list stores Sin. Say S = "abc" = \'a\'->\'b\'->\'c\' in list form, with node \'a\' storing S1n (number of strings that start with "a"), \'b\' storing S2n (number of strings that start with "ab", essentially serving the same function as creating a String "ab" and setting its score). Essentially each node we create (O(1)), we save time / space by refraining from recreating all characters leading up to this node / storing them separately.\n\nFor a complete view of the Trie, say words = ["ab", "ad"], then the node representing "a" would have two children representing "ab" and "ad" respectively (corresponding to \'b\' and \'d\', and at index \'b\' - \'a\' and \'d\' - \'a\' of the node\'s children array, respectively). "a".sz = 2, "ab".sz = 1, "ad".sz = 1.\n\n**Final Approach Implementation**\nEach node N represents the prefix Sj resulted from concatenating all characters from root to N. N.sz = Sjn.\n***Step 1***: Compute all Sjn: For all S, for each prefix Sj, go 1 level deeper into Trie to find the node that represents Sj and increment Sj.sz by 1.\n***Step 2*** : Summing Sjn to get answer : Compute the sum of Sj for each S by dfs on Trie (answer for S = sum of sz for all nodes in the path from root to the end of S, say S = "abc", then answer for S = S1n + S2n + S3n = "a".sz + "ab".sz + "abc".sz, which can be done by dfs in O(n^2) (number of characters in words)). \n\n**Final Complexity:**\nO(# of characters in words) (step 1) + O(# of characters in words) (step 2) = O(n ^ 2) (n = 1000)\n\n**Conclusion:**\nWhen to use Trie? When you want to save repeated computation / string construction for prefixes or suffixes of S. It\'s essentially a compact representation of all prefixes for all S in words. To have a compact representation of all suffixes, simply add each S from back to front to the Trie.\n```\nclass Solution {\n    public class Trie{\n        //number of words that have prefix = the path represented by this Trie node\n        int sz;\n        //children array, ch[i] not null if there is a string with char(i + \'a\') as the next character\n        Trie[] ch;\n        //str is not null if the path represented by this Trie is a String in words, utilized by HashMap below\n        String str;\n        public Trie(){\n            sz = 0;\n            ch = new Trie[26];\n            str = null;\n        }\n    }\n    \n    //computes the answers to the problem by summing sz along the path representing each String in words\n    public void dfs(Trie node, int sum){\n        //sum represents the sum of all sz in the path from root to node\n        sum += node.sz;\n        \n        //put the answer to the string represented by node to map to save repeated computation\n        if(node.str != null){\n            map.put(node.str, sum);\n        }\n        \n        //dfs all non-null children\n        for(Trie child : node.ch){\n            if(child != null){\n                dfs(child, sum);\n            }\n        }\n    }\n    HashMap<String, Integer> map;\n    public int[] sumPrefixScores(String[] words) {\n        map = new HashMap<>();\n        //root, stores no character, root[i] is not null if some string in words starts with char(i + \'a\'), easier to do dfs with this design (can just start at root instead of 26 potential Tries).\n        Trie root = new Trie();\n        \n        //step 1: add each String to Trie iteratively\n        for(String S : words){\n            char[] s = S.toCharArray();\n            Trie cur = root;\n            for(char b : s){\n                int ind = b - \'a\';\n                \n                //make new Trie if no previous string has b as the next character\n                if(cur.ch[ind] == null){\n                    cur.ch[ind] = new Trie();\n                }\n                cur = cur.ch[ind];\n                ++cur.sz;\n            }\n            cur.str = S;\n        }\n        \n\t\t//step 2\n        dfs(root, 0);\n        int[] res = new int[words.length];\n        for(int i = 0; i < words.length; ++i){\n            res[i] = map.get(words[i]);\n        }\n        return res;\n    }\n}\n```\n
['Depth-First Search', 'Trie', 'Java']