CODEWITHSUNDEEP
java
Avv
Avv

Reputation: 519

Comparing 2 strings based on their alphabetical order and frequency

I have the following code below to sort words based on their alphabetical order and their frequency. I understand the main functionality is in Comparator class that does custom sorting based on frequency and alphabetical order of words in reverse order (not default Java order, which is the ascending order).

Question: I am just confused about inner working of Comparator please? Not sure why freq1-freq2 was used but word2.compareTo(word1) and not word2.compareTo(word1)? The requirement is, if 2 words have the same frequency, then we should sort in ascending fashion, but if the two words do not have the same frequency, then the word with largest frequency comes first in priority queue below. I though this implementation of Comparator will cause priority queue to be min priority queue? Please correct me if I am wrong?

import java.util.*;
class TopKWords{
    public List<String> topWords(String[] words, int k) {
        Map<String, Integer> pair = new HashMap<>();
        for(String word: words){
            pair.put(word, pair.getOrDefault(word, 0) + 1);
        }
        
        PriorityQueue<String> pq = new PriorityQueue<>(
            new Comparator<String>(){
                @Override
                public int compare(String word1, String word2){
                    int freq1 = pair.get(word1);
                    int freq2 = pair.get(word2);
                    if(freq1 == freq2) return word2.compareTo(word1);
                    return freq1 - freq2;
                }
            }
        );
        
        for(Map.Entry<String, Integer> entry: pair.entrySet()){
            pq.add(entry.getKey());
            if(pq.size() > k) pq.poll();
        }
        
        List<String> list = new ArrayList<>();
        
        while(!pq.isEmpty()){
            list.add(pq.poll());
        }
        Collections.reverse(list);
        
        return list;
    }
}

Upvotes: 0

Views: 678

Answers (2)

Montaser Majid
Montaser Majid

Reputation: 56

The requirement is, if 2 words have the same frequency, then we should sort in ascending fashion, but if the two words do not have the same frequency, then the word with largest frequency comes first in priority queue below.

There are two cases.

  1. Frequency of two strings are not same. Here higher freq should come first means descending sort.
  2. Frequency of two strings are same. Here ascending sort should be applied.

1st Case

return freq1 - freq2;

It ensures ascending sort. But later it is reversed to ensure descending sort. It is for the first case.

2nd Case

word2.compareTo(word1)

It ensures descending sort (second compared with first). Later reversed to ensure ascending sort. It is the second case.

Simply put, as for 2 cases sorting is different that's why for 1 case, freq1-freq2 is used and for another one word2.compareTo(word1) is used. If both had same sorting then we would have used, freq1-freq2 and word1.compareTo(word2).

Upvotes: 1

Ryan
Ryan

Reputation: 1760

I don't know if this is the most efficient way to do it, but

public class FreqComp implements Comparator<String> {
    private Map<String, Integer> countMap = new HashMap<>();
    
    public FreqComp(String [] data) {
        //initialize the internal map to keep word counts
        for (String word : data) {
            countMap.merge(word, 1, (a, b) -> a+b);
        }
    }
    
    @Override
    public int compare(String o1, String o2) {
        //First get the counts and sort in reverse so the higher number comes first
        Integer cnt1 = countMap.get(o1);
        Integer cnt2 = countMap.get(o2);
        int val = cnt2.compareTo(cnt1);
        if (val == 0) {
            //If it's the same word count, sort alphabetically
            val = o1.compareTo(o2);
        }
        return val;
    }
}

and the use

public static void main(String [] args) {
    String [] words = {"a", "b", "c", "d", "b", "c", "d", "c", "d", "d", "e", "e", "e", "e"};
    Arrays.sort(words, new FreqComp(words));
    System.out.println(Arrays.toString(words));
}

Upvotes: 1

Related Questions