C++ Simple DP solution without Trie (Beats 99% runtime, 97% Space)
Firstly Sort the array of strings without losing original indices (eg: by using vector>).\n\nThis solution takes advantage of the fact that after sorting the st
Firstly Sort the array of strings without losing original indices (eg: by using vector<pair<string,int>>).\n\nThis solution takes advantage of the fact that after sorting the strings with identical prefixes will form a consecutive segment.\n\nExample: \nBefore Sorting => "abc"   "bc"    "ab"   "b"\nAfter Sorting   => **["ab"  "abc"]**    **[  "b"    "bc" ]**\n\nAs you can see for any string **S[i]** strings whose prefix matches with prefix of **S[i]** are either just before **S[i]**\nor just after **S[i]**.\n\nNow I think the solution is pretty self explanotary.\n\n**dp[i][j]** will represent number of strings in the region **words[0, i-1]** whose **prefix[0..j]** matches with **S[0...j]**\nThen reverse the array of strings and calculate the same to find matching strings in the region\n**words[i+1...n-1]**.\n\n// Please look at the code to understand better. \n\n```\nclass Solution {\npublic:\n    int n;\n    vector<int> ans;\n    \n    void calPrefixScore(vector<pair<string,int>> &v)\n    {\n        vector<int> dp(v[0].first.size()), ndp;\n        \n        for(int i = 1; i < n; ++i)\n        {\n            auto [s, idx] = v[i];\n            ndp = vector<int> (s.size(), 0);\n            \n            for(int j = 0; j < min(s.size(), dp.size()); ++j)\n            {\n                if(s[j] != v[i-1].first[j])break;\n                ndp[j] = dp[j] + 1;\n                ans[idx] += ndp[j];\n            }\n            dp = ndp;\n        }\n    }\n    \n    vector<int> sumPrefixScores(vector<string>& words) \n    {\n        n = words.size();\n        ans.resize(n);\n        \n        vector<pair<string,int>> v;\n        for(int i = 0; i < n; ++i){\n            v.push_back({words[i], i});\n        }\n        \n        auto cmp = [&](pair<string,int> &a, pair<string,int> &b){\n            return a.first < b.first;\n        };\n        \n        sort(v.begin(), v.end(), cmp);\n        calPrefixScore(v);\n        \n        reverse(v.begin(), v.end());\n        calPrefixScore(v);\n        \n        for(auto [s, idx] : v){\n            ans[idx] += s.size();\n        }\n        \n        return ans;\n        \n    }\n};\n```\n\n\t\t\t\t\t\t\t\t
['Dynamic Programming', 'Sorting']