["cool_wifi_speed", "water_is_cool", "cold_ice_drink"]

Constraints

1 ≤ Number of reviews ≤ 200
1 ≤ Number of words in a review ≤ 1000
1 ≤ Length of an individual review ≤ 10,000
1 ≤ Number of Good Words ≤ 10,000
1 ≤ Length of an individual Good Word ≤ 4
All words are lowercase (a-z)

Solution

Method 1 – Trie for Good Word Lookup + Stable Sort

Intuition

A Trie allows fast lookup of good words. For each review, count how many words are in the Trie, then sort reviews by this count (goodness value), preserving original order for ties.

Approach

Build a Trie from the list of good words.
For each review:
- Split into words.
- Count how many words are present in the Trie.
Pair each review's index with its goodness value.
Sort the pairs by goodness value descending, preserving original order for ties (stable sort).
Return the sorted indices.

Code

[{"language":"Java","code":"import java.util.*;\n\npublic class Solution {\n    static class TrieNode {\n        Map<Character, TrieNode> children = new HashMap<>();\n        boolean isEnd = false;\n    }\n    static class Trie {\n        TrieNode root = new TrieNode();\n        void insert(String word) {\n            TrieNode node = root;\n            for (char c : word.toCharArray()) {\n                node = node.children.computeIfAbsent(c, k -> new TrieNode());\n            }\n            node.isEnd = true;\n        }\n        boolean search(String word) {\n            TrieNode node = root;\n            for (char c : word.toCharArray()) {\n                if (!node.children.containsKey(c)) return false;\n                node = node.children.get(c);\n            }\n            return node.isEnd;\n        }\n    }\n    public ArrayList<Integer> solve(String A, ArrayList<String> B) {\n        Trie trie = new Trie();\n        for (String word : A.split(\"_\")) trie.insert(word);\n        List<int[]> goodness = new ArrayList<>();\n        for (int idx = 0; idx < B.size(); idx++) {\n            int count = 0;\n            for (String w : B.get(idx).split(\"_\")) {\n                if (trie.search(w)) count++;\n            }\n            goodness.add(new int[]{-count, idx});\n        }\n        goodness.sort(Comparator.comparingInt((int[] a) -> a[0]).thenComparingInt(a -> a[1]));\n        ArrayList<Integer> result = new ArrayList<>();\n        for (int[] pair : goodness) result.add(pair[1]);\n        return result;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">import</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> java.util.</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">*</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span><

Related Tags

Continue Practicing