Anagramme finden

[BaseBallBatBoy]

Hi!

Ich habe ein ArrayList<String>. Die Worte darin möchte ich als Gruppen von Anagrammen zurückgeben.

Beispiel:
{"cat", "foo", "bar", "act", "ofo", "race", "care", "acre"}
returns {{"cat", "act"}, {"bar"}, {"foo", "ofo"}, {"race", "care", "acre"}}

Meinen Versuch seht ihr unten, aber irgendwo ist noch ein fehler drin....
Könnt ihr mir da helfen?

Und übrigens: Ich weiss, dass mein Ansatz nicht der Beste ist. War einfach mal so mein erster Gedanke. Also wenn jemand eine schnellere/schönere/bessere Idee hat: bitte sagen!

import java.util.ArrayList;

public class Anagrams {
	public static void main(String[] args) {  
		ArrayList<String> words = new ArrayList<String>(); 
		
		words.add("cat");
		words.add("foo");
		words.add("bar");
		words.add("act");
		words.add("ofo");
		words.add("race");
		words.add("care");
		words.add("acre");
		
		String[][] resultPairs = new String [words.size()][words.size()];
		resultPairs = organizeIntoAnagrams(words);
		
		for (int i=0; i<words.size(); i++) {
			for (int j=0; j<words.size(); j++) {
				if (!resultPairs[i][j].isEmpty()) {
					System.out.println("resultPairs[" + i + "][" + j + "]: " + resultPairs[i][j].toString());
				}
			}
			System.out.println("---------------------------------------------");
		}
	}
	
	// given {"cat", "foo", "bar", "act", "ofo"} returns {{"cat", "act"}, {"bar"}, {"foo", "ofo"}}	
	public static String[][] organizeIntoAnagrams(ArrayList<String> words) {
			
		// take each string and sort it's chars
		ArrayList<String> sortedWords = new ArrayList<String>(); 
		for (int i=0; i<words.size(); i++) {
			sortedWords.add(i, sort(words.get(i)));
		}
		
		// search for anagrams
		String[][] results = new String [words.size()][words.size()];
		for (int i=0; i<words.size(); i++) {
			
			if (!(sortedWords.get(i)).equals(null)) {
				//safe 1st pair member
				results[i][0] = words.get(i);
				
				int count = 0;
				
				for (int j=0; j<words.size(); j++) {
					if ((sortedWords.get(i)).equals(sortedWords.get(j)) && i != j && !(sortedWords.get(i)).equals(null)) {
						count++;
						results[i][count] = words.get(j);
						
						// remove matching word from list in order to avoid multiple selects
						words.set(j, null);
					}	
				}
				words.set(i, null);
			}
		}
		
		return results;
	}

	public static String sort(String word) {	
		char[] charArray = word.toCharArray();
		java.util.Arrays.sort(charArray);
		return new String(charArray);
	}
}

 

[HonniCilest]

Mhhh, was genau stimmt denn nicht? Ich meine woran merkst du es? Kommt eine Fehlermeldung? Ein falsches Ergebnis? Wie sieht dies aus?

Edit: Hier ein Lösungsansatz von mir (ungetestet!, gibt HasMap statt Array zurück)

public static HashMap<String,ArrayList<String>> organizeIntoAnagrams(ArrayList<String> words) {
            
        // take each string and sort it's chars
        ArrayList<String> sortedWords = new ArrayList<String>(); 
        for (int i=0; i<words.size(); i++) {
            sortedWords.add(i, sort(words.get(i)));
        }
        
        // search for anagrams
        HashMap<String,ArrayList<String>> results = new HashMap<String,ArrayList<String>>();
        for (int i=0; i<words.size(); i++) {
            if(results.containsKey(sortedWords.get(i)))
		results.get(sortedWords.get(i)).add(words.get(i));    
	    else {
		ArrayList<String> al = new ArrayList<String>();
		al.add(words.get(i));
		results.put(sortedWords.get(i),al);
	    }
        }
        
        return results;
    }

 

[BaseBallBatBoy]

Mhhh, was genau stimmt denn nicht? Ich meine woran merkst du es? Kommt eine Fehlermeldung? Ein falsches Ergebnis? Wie sieht dies aus?

Entschuldige, der Fehler ist eine NullPointerException:
resultPairs[0][0]: cat
resultPairs[0][1]: act
Exception in thread "main" java.lang.NullPointerException at Anagrams.main(Anagrams.java:37)

Jedenfalls hat er die erste Gruppe gefunden, aber danach klemmts wohl noch...

PS: Wenn ich dein Code so anschaue, hat HashMap nicht <Key, Value>? Jedenfalls werde ich's mal mit deinem Vorschlag versuchen.


PPS: Hier meine Lösung. War natürlich blöd, ich muss ja schauen ob resultPairs nicht null ist und nicht empty. Anyway, jetzt gehts. Wenn aber jemand einen schöneren Vorschlag hat nur sagen! Ich schau mir in der zwischenzeit mal das mit der HashMap an.

import java.util.ArrayList;

public class Anagrams {
	public static void main(String[] args) {  
		ArrayList<String> words = new ArrayList<String>(); 

		words.add("cat");
		words.add("foo");
		words.add("bar");
		words.add("act");
		words.add("ofo");
		words.add("race");
		words.add("care");
		words.add("acre");
		
		String[][] resultPairs = new String [words.size()][words.size()];
		resultPairs = organizeIntoAnagrams(words);
		
		for (int i=0; i<words.size(); i++) {
			for (int j=0; j<words.size(); j++) {
				if (resultPairs[i][j] != null) {
					System.out.println("resultPairs[" + i + "][" + j + "]: " + resultPairs[i][j].toString());
				}
			}
		}
	}
	
	
	public static String[][] organizeIntoAnagrams(ArrayList<String> words) {
			
		// take each string and sort it's chars
		ArrayList<String> sortedWords = new ArrayList<String>(); 
		for (int i=0; i<words.size(); i++) {
			sortedWords.add(i, sort(words.get(i)));
		}
		
		// search for anagrams
		String[][] results = new String [words.size()][words.size()];
		for (int i=0; i<words.size(); i++) {
			
			if (words.get(i) != null) {
				//safe 1st pair member
				results[i][0] = words.get(i);
				int count = 0;
				
				for (int j=0; j<words.size(); j++) {
					if ((sortedWords.get(i)).equals(sortedWords.get(j)) && i != j && !(sortedWords.get(i)).equals(null)) {
						count++;
						results[i][count] = words.get(j);
						
						// remove matching word from list in order to avoid multiple selects
						words.set(j, null);
					}	
				}
				words.set(i, null);
			}
		}
		return results;
	}

	public static String sort(String word) {	
		char[] charArray = word.toCharArray();
		java.util.Arrays.sort(charArray);
		return new String(charArray);
	}
}

 

[HonniCilest]

Ja stimmt den Key muss man auch noch einen Typ zuweisen.