LintCode 1883 · Top K Frequently Mentioned Keywords.java

	public class Solution {
	/**
	* @param K: a integer
	* @param keywords: a list of string
	* @param reviews: a list of string
	* @return: return the top k keywords list
	*/
	public List<String> TopkKeywords(int K, String[] keywords, String[] reviews) {
	// write your code here
	if (keywords == null) {
	return new ArrayList<>(0);
	}
	Set<String> keys = new HashSet<>();
	for (String keyword : keywords) {
	keys.add(keyword);
	}
	Map<String, Integer> word2Counts = new HashMap<>();
	Map<String, Integer> keys2Counts = new HashMap<>();
	for (String review : reviews) {
	Set<String> tmpSet = new HashSet<>();
	String[] words = review.split("\\P{Alpha}+");
	for (String word : words) {
	tmpSet.add(word.toLowerCase());
	}
	// for each review, if a keyword is hit, ++
	for (String uniqueWord : tmpSet) {
	if (keys.contains(uniqueWord)) {
	keys2Counts.put(uniqueWord, keys2Counts.getOrDefault(uniqueWord, 0) + 1);
	}
	}
	}
	Queue<KeyWithFrequency> queue = new PriorityQueue<>(K, new MyComparator());
	for (Map.Entry<String, Integer> entry : keys2Counts.entrySet()) {
	queue.add(new KeyWithFrequency(entry.getKey(), entry.getValue()));
	if (queue.size() > K) {
	queue.poll();
	}
	}
	// System.out.println("queue=" + queue);
	LinkedList<String> result = new LinkedList<>();
	while(!queue.isEmpty()) {
	result.addFirst(queue.poll().key);
	}
	return result;
	}
	private class MyComparator implements Comparator<KeyWithFrequency>{
	@Override
	public int compare(KeyWithFrequency o1, KeyWithFrequency o2) {
	int result = o1.frequency - o2.frequency;
	if (result == 0) {
	result = o2.key.compareTo(o1.key);
	}
	return result;
	}
	}
	private class KeyWithFrequency {
	String key;
	int frequency;
	KeyWithFrequency(String key, int frequency) {
	this.key = key;
	this.frequency = frequency;
	}
	@Override
	public String toString() {
	return "key=" + key + "; frequency=" + frequency;
	}
	}
	}

view raw LintCode 1883 · Top K Frequently Mentioned Keywords.java hosted with ❤ by GitHub