Restaurant Reviews Editorial

Practice Problem Link: Restaurant Reviews

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A restaurant listing website has asked you to analyze the reviews on its restaurants.
The reviews need to be sorted by how good they are, the best reviews go on top. The goodness a review is determined by the number of times "good words" appear in them. You are given a list of good words.

Given n reviews and m good words, sort the reviews, such that the one with the most good words appears first. For reviews with the same number of good words, maintain the initial order.

Approach

The approach in this problem is to use a simulation for what is said in the statement in a smarter manner. We will basically traverse on the list of reviews and for each review, try to find the number of good words in it by using a HashSet or HashMap to obtain constant lookup times. We can store the pair of {number of good words, i} for the ith review and sort our array in the manner asked in the question using a custom comparator to return the output in the required manner.

Analysis

• Time Complexity: O(n * m * |word length|)
• Space Complexity: O(n)

Implementation

C++

vector<string> orderReviews(vector<string> &reviews, vector<string> &goodWords) {
    set<string> words(goodWords.begin(), goodWords.end());
	int n = reviews.size();
	pair<int, int> goodness[n];
	vector<string> output(n);
	for (int i = 0; i < n; i++) {
		string review = reviews[i];
		int m = review.length();
		int numGoodWords = 0;
		int s = 0;
		for (int j = 0; j < m; j++) {
			if (review[j] == ' ') {
				if (words.find(review.substr(s, j - s)) != words.end()) {
					numGoodWords++;
				}
				s = j + 1;
			}
		}
		if (words.find(review.substr(s)) != words.end()) {
			numGoodWords++;
		}
		pair<int, int> goodnessi = {numGoodWords, i};
		goodness[i] = goodnessi;
	}
	sort(goodness, goodness + n, [&] (pair<int, int> &p1, pair<int, int> &p2) {
		if(p1.first < p2.first) {
			return p1.first < p2.first;
		}
		else {
			if(p1.first == p2.first) {
				return p1.second >= p2.second;
			}
			else {
				return p1.first < p2.first;
			}
		}
	});
	reverse(goodness, goodness + n);
	for (int i = 0; i < n; i++) {
		output[i] = reviews[goodness[i].second];
	}
	return output;
}

Java

class GoodnessComparator implements Comparator<int[]> {
    public int compare(int[] a, int[] b) {
		if (a[0] < b[0]) {
			return 1;
		}
		if (a[0] == b[0]) {
			if (a[1] < b[1]) {
				return -1;
			} else {
				return 1;
			}
		}
		return -1;
    }
}
class Solution {
	String[] orderReviews(String[] reviews, String[] goodWords) {
	    // add your logic here
		Set<String> words = new HashSet<>(Arrays.asList(goodWords));
		int n = reviews.length;

		int[][] goodness = new int[n][2];
		String[] output = new String[n];
		for (int i = 0; i < n; i++) {
			String review = reviews[i];
			int m = review.length();
			int numGoodWords = 0;
			int s = 0;
			for (int j = 0; j < m; j++) {
				if (review.charAt(j) == ' ') {
					if (words.contains(review.substring(s, j))) {
						numGoodWords++;
					}
					s = j + 1;
				}
			}
			if (words.contains(review.substring(s))) {
				numGoodWords++;
			}
			int[] goodnessi = {numGoodWords, i};
			goodness[i] = goodnessi;
		}
		Arrays.sort(goodness, new GoodnessComparator());
		for (int i = 0; i < n; i++) {
			output[i] = reviews[goodness[i][1]];
		}
		return output;
	}
}

Alternative Approach

Alternatively, we can use Trie to solve this problem. We can construct a Trie on the Good Words, and by traversing on our Trie, we can check if the review string has some good word in it and keep its count. Finally we sort the result using a custom comparator, and return the output.

Analysis

• Time Complexity: O(n * |word length|)
• Space Complexity: O(n)

Implementation

C++

class TrieNode {
private:
    TrieNode* children[26];
    bool isEnd = false;
public:
    bool hasWord(string w) {
        TrieNode* nextNode = this;
        for (int i = 0; i < w.size(); i++) {
            nextNode = nextNode->children[w[i] - 'a'];
            if (!nextNode) {
                return false;
            }
            if (i == w.size() - 1) {
                return nextNode->isEnd;
            }
        }
        return false;
    }
    void addWord(string w) {
        TrieNode* nextNode = this;
        for (int i = 0; i < w.size(); i++) {
            int nextIndex = w[i] - 'a';
            if (!nextNode->children[nextIndex]) {
                nextNode->children[nextIndex] = new TrieNode();
            }
            nextNode = nextNode->children[nextIndex];
            if (i == w.size() - 1) {
                nextNode->isEnd = true;
                return;
            }
        }
    }
};

bool compPairDesc(const pair<int,int> &a, const pair<int,int> &b) {
    if (a.first > b.first) {
		return true;
	}
	if (a.first == b.first && a.second < b.second) {
		return true;
	}
	return false;
}

vector<string> orderReviews(vector<string> &reviews, vector<string> &goodWords) {
    vector<string> output(reviews.size());
    TrieNode* root = new TrieNode();
    for (int i = 0; i < goodWords.size(); i++) {
        root->addWord(goodWords[i]);
    }
    vector<pair<int, int>> goodness;
    for (int i = 0; i < reviews.size(); i++) {
        string review = reviews[i];
        int numGoodWords = 0;
        int s = 0;
        for (int j = 0; j < review.size(); j++) {
            if (review[j] == ' ') {
                if (root->hasWord(review.substr(s, j - s))) {
                    numGoodWords++;
                }
                s = j + 1;
            }
        }
        if (root->hasWord(review.substr(s, review.size() - s))) {
            numGoodWords++;
        }
        goodness.push_back(make_pair(numGoodWords, i));
    }
    sort(goodness.begin(), goodness.end(), compPairDesc);
    for (int i = 0; i < reviews.size(); i++) {
        output[i] = reviews[goodness[i].second];
    }
    return output;
}

Java

class Solution {
	class Pair {
		int first, second;
		Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}
	class TrieNode {
		TrieNode[] children = new TrieNode[26];
		boolean isEnd = false;
		public boolean hasWord(String w) {
			TrieNode nextNode = this;
			for (int i = 0; i < w.length(); i++) {
				nextNode = nextNode.children[w.charAt(i) - 'a'];
				if (nextNode == null) {
					return false;
				}
				if (i == w.length() - 1) {
					return nextNode.isEnd;
				}
			}
			return false;
		}
		public void addWord(String w) {
			TrieNode nextNode = this;
			for (int i = 0; i < w.length(); i++) {
				int nextIndex = w.charAt(i) - 'a';
				if (nextNode.children[nextIndex] == null) {
					nextNode.children[nextIndex] = new TrieNode();
				}
				nextNode = nextNode.children[nextIndex];
				if (i == w.length() - 1) {
					nextNode.isEnd = true;
					return;
				}
			}
		}
	}

	String[] orderReviews(String[] reviews, String[] goodWords) {
		String[] output = new String[reviews.length];
		TrieNode root = new TrieNode();
		for (int i = 0; i < goodWords.length; i++) {
			root.addWord(goodWords[i]);
		}
		Pair[] goodness = new Pair[reviews.length];
		int goodnessIndx = 0;
		for (int i = 0; i < reviews.length; i++) {
			String review = reviews[i];
			int numGoodWords = 0;
			int s = 0;
			for (int j = 0; j < review.length(); j++) {
				if (review.charAt(j) == ' ') {
					if (root.hasWord(review.substring(s, j))) {
						numGoodWords++;
					}
					s = j + 1;
				}
			}
			if (root.hasWord(review.substring(s, review.length()))) {
				numGoodWords++;
			}
			goodness[goodnessIndx++] = (new Pair(numGoodWords, i));
		}
		Arrays.sort(goodness, new Comparator<Pair> () {
			public int compare(Pair a, Pair b) {
				if(a.first < b.first) {
					return 1;
				}
				if(a.first == b.first && a.second > b.second) {
					return 1;
				}
				return - 1;
			}
		});
		for (int i = 0; i < reviews.length; i++) {
			output[i] = reviews[goodness[i].second];
		}
		return output;
	}
}