Finding Anagrams

A very simple way to find all anagram classes. example is mainly to illustrate the use of the Dictionary class (defined is class and your Project#5), and also a sample implementation of the two sorting algorithms discussed in class.



 

import java.awt.*;
import java.applet.Applet;

public class Anagrams extends Applet {

	Dictionary D = new Dictionary();
	int N = D.nWords;					// number of words
	
	// dict is the dictionary of words, and signature is their sigs
	String[] dict, signature;
	
	// Gui
	TextArea text;
	
	public void init() {
	
		makeGui();
		
		dict = new String[N];
		signature = new String[N];
		
		// set up dictionary and form signatures
		for (int i=0; i < N; i++) {
			// Get the ith word from the dictionary
			dict[i] = D.getWordAt(i);
			//signature[i] = dict[i];
			// For its signature
			signature[i] = formSignature(dict[i]);
		}
		
		text.appendText(N+" words processed.\n\n");
		
		// sort signatures (and corresponding dict entries)
		dictSort(dict, signature, N);
		
		
	} // init
	
	public void paint(Graphics g) {
		// scan the array for anagrams and print the anagram classes
		for (int i = 0; i < N-1; i++) {
			if (signature[i].equals(signature[i+1])) {
				// found an anagram class
				// print the first word in the class
				text.appendText(dict[i]);
				// Run through the rest and print them
				do {
					i++;
					text.appendText(" " + dict[i]);
				} while (signature[i].equals(signature[i+1]));
				text.appendText("\n");
			}
		}
	} // paint
	
	private void dictSort(String[] w, String[] s, int n) {
		// we will use insertion sort here
		String e1, e2;
		int p;
		
		for (int i = 1; i < n; i++) {
			// insert s[i] in s[0]..s[i]
			e1 = s[i];
			e2 = w[i];
			for (p = i; p > 0 && (e1.compareTo(s[p-1]) < 0); p--) {
				s[p] = s[p-1];
				w[p] = w[p-1];
			}
			
			// place e1 in s[p]
			s[p] = e1;
			w[p] = e2;
		}
	
	} //dictSort
	
	private String formSignature(String s) {
	
		char[] word = s.toCharArray();
		int n = s.length();
		int p;
		char temp;
		
		// sort letters in word (using selection sort)
		for (int i = 0; i < n-1; i++) {
			// place find the smallest char in word[i]..word[n-1]
			p = i;
			for (int j = i+1; j < n; j++)
				if (word[j] < word[p])
					p = j;
			
			// Swap word[i] and word[p]
			temp = word[i];
			word[i] = word[p];
			word[p] = temp;
		}
		
		s = new String(word);
		return s;
	} // formSignature
	
	private void makeGui() {
	
		// The applet has a textArea
		text = new TextArea("Anagrams\n-------------\n\n", 20, 40, TextArea.SCROLLBARS_BOTH);
		text.setBackground(new Color(255, 153, 0));
		add(text);
	} // makeGui

} // Anagrams