Sorting&Searching 基于变位词的字符串数组排序 @CareerCup - JAVA

两种排序结果不一样。。。

1 实现Comparator接口的compare方法，在里面先把每个string都排序一遍，然后再比较

2 用一个Hashtable>的结构，String为排序后的确定的string，LL里面装着各种anagram的变种

package Sorting_Searching;  
  
import java.util.Arrays;  
import java.util.Comparator;  
import java.util.Hashtable;  
import java.util.LinkedList;  
  
import CtCILibrary.AssortedMethods;  
  
/** 
 * Write a method to sort an array of strings so that all the anagrams are next 
 * to each other. 
 *  
 * 译文： 
 *  
 * 写一个函数对字符串数组排序，使得所有的变位词都相邻。 
 *  
 */  
public class S11_2 {  
    public static void main(String[] args) {  
        String[] array1 = { "apple", "banana", "carrot", "ele", "duck", "papel",  
                "tarroc", "cudk", "eel", "lee" };  
        System.out.println(AssortedMethods.stringArrayToString(array1));  
        Arrays.sort(array1, new AnagramComparator());  
        System.out.println(AssortedMethods.stringArrayToString(array1));  
          
        String[] array2 = { "apple", "banana", "carrot", "ele", "duck", "papel",  
                "tarroc", "cudk", "eel", "lee" };  
        sort(array2);  
        System.out.println(AssortedMethods.stringArrayToString(array2));  
    }  
      
    static class AnagramComparator implements Comparator




{  
  
        @Override  
        public int compare(String s1, String s2) {  
            String sorted1 = sortChars(s1);  
            String sorted2 = sortChars(s2);  
            return sorted1.compareTo(sorted2);  
        }  
    }  
      
    public static String sortChars(String s){  
        char[] ch = s.toCharArray();  
        Arrays.sort(ch);  
        return new String(ch);  
    }  
      
    public static void sort(String[] array) {  
        Hashtable> hash = new Hashtable>();  
          
        // Group words by anagram  
        for(String s : array){  
            String key = sortChars(s);  
            if(!hash.containsKey(key)){  
                hash.put(key, new LinkedList());  
            }  
            LinkedList anagrams = hash.get(key);  
            anagrams.push(s);  
        }  
          
        // Convert hash table to array  
        int index = 0;  
        for(String key : hash.keySet()){  
            LinkedList anagrams = hash.get(key);  
            for(String t : anagrams){  
                array[index++] = t;  
            }  
        }  
    }  
      
}