Thought process explained | Trie | For beginner
So First question?\n How I got to know that Trie will work.\n\t So let\'s thing :\n\t We have 1000 words of 1000 length each. Also we have to get the value for 
## So First question?\n* How I got to know that Trie will work.\n\t* So let\'s thing :\n\t* We have 1000 words of 1000 length each. Also we have to get the value for substring also.\n\t\t* Will HashMap works? No because for 1k word of 1k length, going to store all substring that would cause TLE.\n\t* So let\'s think somethink else :\n\t\t* We don\'t want to generate substring of string.\n\t\t* We want to get the res of [0-i-th] substring contest time.\n\t\t* We also want to store the freq.\n\t\t* So from above point it\'s clear that,\n\t\t\t* If we can store frequency of each substring [0,ith] and get the value for any string in O(N) that will help here.\n\t\t\t* This point revoked my to use Trie.\n\t\t\t* So Data Structure like trie, we have first problem, What data trie will contains and how to handle it?\n\t\t\t* for that let\'s think what data we need except basic Structure of Trie?\n\t\t\t\t* At any i-th position in string what we want?\n\t\t\t\t\t* Number of times this subtring [0, ith] appeared in entire list.\n\t\t\t\t\t* That\'s means number of time current node visited. Right?\n\t\t\t\t\t* Storing count for each node would help.\n\nSo from above point we come up with conclusioin to use Trie with bellow Structure.\n```\nclass Trie {\n    public :\n    unordered_map<char, Trie*> children;\n    int cnt;\n    Trie() {\n        cnt = 0;\n    }\n    int getCnt() {\n        return cnt;\n    }\n};\n```\n\n## Now let\'s implement :\n* First insert all the string from given list into the Trie.\n* Traverse trie and for each string, at keep sum of number of times all node visited which came in the path of string i-th\n* This count is your answer.\n\n```\nclass Solution {\npublic:\n    Trie *trie;\n    void insert(string &str) {\n        Trie * temp = trie;\n        for(char &ch : str) {\n            if(temp->children.count(ch) == 0) {\n                temp->children[ch] = new Trie();\n            }\n            temp = temp->children[ch];\n            temp->cnt++;\n        }\n    }\n    \n    int getCnt(string &s) {\n        int cnt = 0;\n        Trie *root = trie;\n        for(char &ch : s) {\n            cnt+=root->getCnt();\n            root = root->children[ch];\n        }\n        return cnt+root->getCnt();\n    }\n    \n    vector<int> sumPrefixScores(vector<string>& words) {\n        trie = new Trie();\n        for(string &s : words) insert(s);\n        vector<int> res;\n        for(string &s : words) {\n            res.push_back(getCnt(s));\n        }\n        return res;\n    }\n```\n\n## Time Complexity \n* Inserting and traversing String into Trie will cause of O(N).\n* So for N string it\'ll be O(N*N) that would be accepted.\n\n## Space Complexity\n* Space complexity will be O(alphabet_size * average key length * N).\n\n\n**Please upvote if it helps.**\n**Happy Coding**
[]