SHARE
TWEET

Untitled

a guest Jan 24th, 2020 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. class Solution {
  4.   /**
  5.    * Sorts a list of words using MSD radix sort.
  6.    *
  7.    * @param words
  8.    *     The list of words to sort.
  9.    * @return The sorted list of words.
  10.    * @throws NullPointerException
  11.    *     If `words` equals `null`.
  12.    */
  13.   static List<String> radixSortMSD(List<String> words) {
  14.    
  15.   return radixSortMSD(words, 0);
  16.  
  17.   }
  18.  
  19.   @SuppressWarnings("all")
  20.   static List<String> radixSortMSD(List<String> words, int index){
  21.    
  22.     //bucketering
  23.    
  24.     if(index > maxWord(words)) return words;
  25.    
  26.     List<String>[] buckets = new ArrayList[27];
  27.    
  28.     buckets[0] = new ArrayList<String>();
  29.      
  30.     Iterator<String> itr = words.iterator();
  31.    
  32.     while(itr.hasNext()){
  33.    
  34.       String word = itr.next();
  35.      
  36.       if(index == word.length()){
  37.         buckets[0].add(word);
  38.         continue;
  39.       }
  40.      
  41.       int bucket = Integer.valueOf(word.charAt(index)) - 96;
  42.      
  43.       if(buckets[bucket] == null) buckets[bucket] = new ArrayList<String>();
  44.      
  45.       buckets[bucket].add(word);
  46.      
  47.     }
  48.    
  49.     for(int k = 0; k < 27; k++){
  50.      
  51.       if(buckets[k] == null) continue;
  52.      
  53.       buckets[k] = radixSortMSD(buckets[k], index+1);
  54.  
  55.     }
  56.    
  57.     words = unbuckify(buckets);
  58.    
  59.     return words;
  60.    
  61.      
  62.     }
  63.  
  64.  
  65.   static ArrayList<String> unbuckify(List<String>[] buckets){
  66.    
  67.     ArrayList<String> ret = new ArrayList<String>();
  68.    
  69.     for(int k = 0; k < 27; k++){
  70.      
  71.       if(buckets[k]==null) continue;
  72.      
  73.       ret.addAll(buckets[k]);
  74.      
  75.     }
  76.    
  77.     return ret;
  78.    
  79.    
  80.   }
  81.  
  82.  
  83.  
  84.   static int maxWord(List<String> words){
  85.    
  86.     int max  = 0;
  87.    
  88.     Iterator<String> itr = words.iterator();
  89.    
  90.     while(itr.hasNext()){
  91.       String word = itr.next();
  92.       if(word.length() > max) max = word.length();
  93.     }
  94.    
  95.     return max;
  96.   }
  97.  
  98.  
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top