Problem

Given a set of hotel reviews and a string containing “Good Words”, sort the reviews in descending order of their “Goodness Value” (number of good words in the review). Sorting should be stable: if two reviews have the same goodness value, preserve their original order.

You are expected to use a Trie for efficient good word lookup.

Input

  • S: String of good words separated by "_"
  • R: List of review strings, each review’s words separated by "_"

Output

  • List of original indices of reviews in sorted order by goodness value (descending, stable)

Examples

Example 1

1
2
3
4
5
6
7

Input:
S = "cool_ice_wifi"
R = ["water_is_cool", "cold_ice_drink", "cool_wifi_speed"]

Output:
[2, 0, 1]
Explanation: Sorted reviews are ["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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.*;

public class Solution {
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEnd = false;
    }
    static class Trie {
        TrieNode root = new TrieNode();
        void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.computeIfAbsent(c, k -> new TrieNode());
            }
            node.isEnd = true;
        }
        boolean search(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (!node.children.containsKey(c)) return false;
                node = node.children.get(c);
            }
            return node.isEnd;
        }
    }
    public ArrayList<Integer> solve(String A, ArrayList<String> B) {
        Trie trie = new Trie();
        for (String word : A.split("_")) trie.insert(word);
        List<int[]> goodness = new ArrayList<>();
        for (int idx = 0; idx < B.size(); idx++) {
            int count = 0;
            for (String w : B.get(idx).split("_")) {
                if (trie.search(w)) count++;
            }
            goodness.add(new int[]{-count, idx});
        }
        goodness.sort(Comparator.comparingInt((int[] a) -> a[0]).thenComparingInt(a -> a[1]));
        ArrayList<Integer> result = new ArrayList<>();
        for (int[] pair : goodness) result.add(pair[1]);
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def solve(self, A: str, B: list[str]) -> list[int]:
        class TrieNode:
            def __init__(self):
                self.children = {}
                self.is_end = False
        class Trie:
            def __init__(self):
                self.root = TrieNode()
            def insert(self, word: str):
                node = self.root
                for c in word:
                    if c not in node.children:
                        node.children[c] = TrieNode()
                    node = node.children[c]
                node.is_end = True
            def search(self, word: str) -> bool:
                node = self.root
                for c in word:
                    if c not in node.children:
                        return False
                    node = node.children[c]
                return node.is_end
        trie = Trie()
        for word in A.split('_'):
            trie.insert(word)
        goodness = []
        for idx, review in enumerate(B):
            count = sum(trie.search(w) for w in review.split('_'))
            goodness.append((-count, idx))
        goodness.sort()
        return [idx for _, idx in goodness]

Complexity

  • ⏰ Time complexity: O(G + N*L), where G is total good word chars, N is number of reviews, L is average review length.
  • 🧺 Space complexity: O(G + N), for the Trie and result list.