Hotel Reviews

Given a set of reviews provided by the customers for different hotels and a string containing “Good Words”, you need to sort the reviews in descending order according to their “Goodness Value” (Higher goodness value first). We define the “Goodness Value” of a string as the number of “Good Words” in that string.

Note: Sorting should be stable. If review i and review j have the same “Goodness Value” then their original order would be preserved.

 You are expected to use Trie in an Interview for such problems 

1.   1 <= No.of reviews <= 200
2.   1 <= No. of words in a review <= 1000
3.   1 <= Length of an individual review <= 10,000
4.   1 <= Number of Good Words <= 10,000
5.   1 <= Length of an individual Good Word <= 4
6.   All the alphabets are lower case (a - z)

S : A string S containing "Good Words" separated by  "_" character. (See example below)
R : A vector of strings containing Hotel Reviews. Review strings are also separated by "_" character.

A vector V of integer which contain the original indexes of the reviews in the sorted order of reviews. 

V[i] = k  means the review R[k] comes at i-th position in the sorted order. (See example below)
In simple words, V[i]=Original index of the review which comes at i-th position in the sorted order. (Indexing is 0 based)

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

Output:
ans = [2, 0, 1]
Here, sorted reviews are ["cool_wifi_speed", "water_is_cool", "cold_ice_drink"]

Solution:

Time: O(nlogn)
Space: O(n)

public class Solution {
    static class Entry {
        int index;
        int freq;
        
        public Entry(int freq, int i) {
            this.index = i;
            this.freq = freq;
        }
    }
    
    public ArrayList<Integer> solve(String A, ArrayList<String> B) {
        ArrayList<Integer> result = new ArrayList<>();
        Set<String> words = new HashSet<>();
        String[] arr = A.split("_");
        for (String w : arr) {
            words.add(w);
        }
        ArrayList<Entry> list = new ArrayList<>();
        for (int i = 0; i < B.size(); i ++) {
            String s = B.get(i);
            String[] ss = s.split("_");
            int freq = 0;
            for (String word : ss) {
                if (words.contains(word)) {
                    freq ++;
                }
            }
            list.add(new Entry(freq, i));
        }
        Collections.sort(list, new Comparator<Entry>(){
            @Override
            public int compare(Entry a, Entry b) {
                int freqComp = Integer.compare(b.freq, a.freq);
                if (freqComp == 0) {
                    return Integer.compare(a.index, b.index);
                }
                return freqComp;
            }
        });
        for (Entry e : list) {
            result.add(e.index);
        }
        return result;
    }
}