Skip to content

Instantly share code, notes, and snippets.

@enif-lee
Last active January 1, 2017 10:42
Show Gist options
  • Save enif-lee/af649ca28e2c03e8559df1f6c918845c to your computer and use it in GitHub Desktop.
Save enif-lee/af649ca28e2c03e8559df1f6c918845c to your computer and use it in GitHub Desktop.
package problem.boj;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
/**
* Created by Jinseoung on 2017-01-01.
*/
public class AnagramGroup {
static Scanner sc = new Scanner(ClassLoader.getSystemResourceAsStream("problem/boj/AnagramGroup.testcase"));
static Word[] redixSort (Word[] words) {
int maxLength = getMaxLength(words);
for(int index = 1; index <= maxLength; index++) {
Word[] newWords = new Word[words.length];
int[] counts = new int[27];
for(int i = 0; i < words.length; i++) {
Word word = words[i];
counts[index >= word.length ? 26 : word.counts[word.length-index]-'a']++;
}
for(int i = 1; i < 27; i++) counts[i] += counts[i-1];
for(int i = words.length-1; i >= 0; i--) {
Word word = words[i];
newWords[--counts[index >= word.length ? 26 : word.counts[word.length-index]-'a']] = word;
}
words = newWords;
}
return words;
}
static int getMaxLength (Word[] strings) {
int result = 0;
for(int i = 0; i < strings.length; i++){
if(result < strings[i].length) result = strings[i].length;
}
return result;
}
static class Word {
String word;
char[] counts;
int length = 0;
public Word(String word) {
this.word = word;
this.length = word.length();
this.counts = new char[word.length()];
int[] counts = new int[26];
int countsPosition = 0;
for(int i = 0 ; i < word.length(); i++) {
counts[word.charAt(i)-'a']++;
}
// counting sort
for(int i = 0; i < 26; i++) {
for(int j = 0; j < counts[i]; j++) {
this.counts[countsPosition++] = (char) (i + 'a');
}
}
}
}
static class Anagram {
int count=1;
String word;
ArrayList<String> words = new ArrayList<>();
String counts;
public Anagram(String word, String counts) {
this.word = word;
this.words.add(word);
this.counts = counts;
}
public boolean equals(Anagram obj) {
return counts.equals(obj.counts);
}
public void merge(Anagram anagram) {
if(this.word.compareTo(anagram.word) > 0) {
this.word = anagram.word;
}
words.add(anagram.word);
this.count++;
}
public String getWords () {
StringBuilder stringBuilder = new StringBuilder();
words.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
for(String word : words) {
stringBuilder.append(word + " ");
}
return stringBuilder.toString();
}
public String getFormat() {
return String.format("Group of size %d: %s.", count, getWords());
}
}
public static void main(String[] args) {
ArrayList<Word> wordArrayList = new ArrayList<>();
while(sc.hasNext()){
wordArrayList.add(new Word(sc.next()));
}
Word[] words = redixSort(wordArrayList.toArray(new Word[]{}));
ArrayList<Anagram> anagrams = new ArrayList<>();
Anagram anagram = new Anagram(words[0].word, new String(words[0].counts));
for(int i = 1; i < words.length; i++){
Anagram newerAnagram = new Anagram(words[i].word, new String(words[i].counts));
if(anagram.equals(newerAnagram)) {
anagram.merge(newerAnagram);
} else {
anagrams.add(anagram);
anagram = newerAnagram;
}
}
anagrams.add(anagram);
Collections.sort(anagrams, (o1, o2) -> {
if(o1.count == o2.count) {
return o1.word.compareTo(o2.word);
}
return o2.count - o1.count;
});
for(int i = 0 ; i < 5; i++) {
System.out.println(anagrams.get(i).getFormat());
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment