Fastest Solution in Java with Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal of this problem is to calculate a score for each word, where the score is the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal of this problem is to calculate a score for each word, where the score is the sum of lengths of common prefixes between the word and every other word in the input array. To efficiently compute this, sorting the words and processing them in a way that allows us to compare neighboring words for common prefixes is a good approach. By using sorted indices, we can minimize comparisons and efficiently accumulate the prefix scores for each word.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the words by lexicographical order: This ensures that words with imilar prefixes are next to each other, allowing for easier comparison.\n\n2. Calculate the lengths of common prefixes: For each adjacent pair of sorted words, compute the length of their common prefix. Store these lengths for further use.\n\n3. Compute prefix scores:\n- For each word, add its full length to its score.\n- Then, for each word, compare it with subsequent words, using the precomputed common prefix lengths to avoid unnecessary recomputations. Add these common prefix lengths to the score for both words involved.\n4. Return the result: After computing the prefix scores for all words, return the result array.\n# Complexity\n- Time complexity:O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        int wordCount = words.length;\n        Integer[] sortedIndices = new Integer[wordCount];\n        for (int i = 0; i < wordCount; i++) {\n            sortedIndices[i] = i;\n        }\n        Arrays.sort(sortedIndices, (a, b) -> words[a].compareTo(words[b]));\n        \n        int[] commonPrefixLengths = calculateCommonPrefixLengths(words, sortedIndices);\n        int[] scores = calculateScores(words, sortedIndices, commonPrefixLengths);\n        return scores;\n    }\n\n    private int[] calculateCommonPrefixLengths(String[] words, Integer[] sortedIndices) {\n        int[] commonPrefixLengths = new int[words.length];\n        for (int i = 1; i < words.length; i++) {\n            String prevWord = words[sortedIndices[i - 1]];\n            String currWord = words[sortedIndices[i]];\n            int commonLength = 0;\n            while (commonLength < prevWord.length() && \n                   commonLength < currWord.length() && \n                   prevWord.charAt(commonLength) == currWord.charAt(commonLength)) {\n                commonLength++;\n            }\n            commonPrefixLengths[i] = commonLength;\n        }\n        return commonPrefixLengths;\n    }\n\n    private int[] calculateScores(String[] words, Integer[] sortedIndices, int[] commonPrefixLengths) {\n        int[] scores = new int[words.length];\n        for (int i = 0; i < sortedIndices.length; i++) {\n            int wordIndex = sortedIndices[i];\n            int wordLength = words[wordIndex].length();\n            scores[wordIndex] += wordLength;\n            int j = i + 1;\n            int commonLength = wordLength;\n            while (j < words.length) {\n                commonLength = Math.min(commonLength, commonPrefixLengths[j]);\n                if (commonLength == 0) {\n                    break;\n                }\n                scores[wordIndex] += commonLength;\n                scores[sortedIndices[j]] += commonLength;\n                j++;\n            }\n        }\n        return scores;\n    }\n}\n```
['Array', 'String', 'Trie', 'Counting', 'Java']