An anagram is a word obtained by reordering the letters of another word. For exa

Question

An anagram is a word obtained by reordering the letters of another word. For example, "once" and "cone" are anagrams. Note that each letter must be reused exactly once, so anagrams must have the same number of letters. Which word in the English language has the most anagrams? Let us take "words in the English language" to mean words in the file "words.txt" located here: http://www.greenteapress.com/thinkpython/code/words.txt

Write a program to solve this problem using the EList.java class:

public class Elist<E> {
  private E[] a;
  private int size;
  private final int INITIAL_SIZE = 10;
  private int count = 0;

  /** Constructor creates an empty list. */
  Elist() {
    a = (E[]) new Object[INITIAL_SIZE];
    size = INITIAL_SIZE;
  }

  /**
   * Add object to end of list, extending array if necessary. This is the only
   * method that may call extend().
   */
  public void addToEnd(E o) {
    if (count == a.length)
      extend();
    a[count] = o;
    ++count;
  }

  /** Return index if o is present, else -1. */
  public int indexOf(E o) {
    for (int i = 0; i < count; ++i)
      if (a[i].equals(o))
        return i;
    return -1;
  }

  public int size() {
    return count;
  }

  public boolean isEmpty() {
    return count == 0;
  }

  /**
   * For simplicity, in the following we ignore error checking for valid
   * indexes.
   */
  public E get(int i) {
    return a[i];
  }

  public E set(int i, E o) {
    E t = a[i];
    a[i] = o;
    return t;
  }

  /** Add object to index i, making room by shifting to right. */

  public void add(int i, E o) {
    if ((i == 0) && this.isEmpty())
      addToEnd(o);
    else {
      addToEnd(a[count - 1]); // this deals with extend if necessary
      for (int j = count; j > i; j--)
        a[j] = a[j - 1];
      a[i] = o;
    }
  }

  public E remove(int i) {
    E t = a[i];
    for (int j = i; j < count - 1; ++j)
      a[j] = a[j + 1];
    --count;
    return t;
  }
  
  public int contains(E o){
    /*
    for(E e: a)
     
      if(o.equals(e))
        return true;
    return false;
    */
    for(int i=0;i<count;++i)
      if(a[i].equals(o))
        return i;
    return -1;
  }

  private void extend() {
    // E[] b = (E[]) new Object[2 * a.length];
    E[] b = (E[]) new Object[2*a.length];
    for (int i = 0; i < a.length; ++i)
      b[i] = a[i];
    a = b;
  }

  public String toString() {
    String s = "[";
    for (int i = 0; i < count; i++) {
      if (i > 0)
        s += ", "; // separate entries by commas
      s += a[i];
    }
    return s + "]";
  }
}

Explanation / Answer

public class AnagramSolver {

static Dictionary dictionary;
String temp=" ";
  
public AnagramSolver(Dictionary d)
{
this.dictionary=d;

}

public static String solve(String s)
{
double before = System.currentTimeMillis();
dictionary.contains(s);
double after = System.currentTimeMillis();
if(dictionary.contains(s))
return s;
else
return null;
}

public static void main (String args[]) throws Exception
{

  if(args[2].equals("b"))
{
BinaryDictionary b=new BinaryDictionary(args[1]); // Click here Binary Dictionary code
   AnagramSolver as=new AnagramSolver(b);
  }
else if (args[2].equals("l"))
{
LinearDictionary l=new LinearDictionary(args[1]); // Click here Linear Dictionary code
AnagramSolver as=new AnagramSolver(l);
}
else if(args[2].equals("h"))
  {
HashDictionary h=new HashDictionary(args[1]);   // Click here Hash Dictionary code
AnagramSolver as=new AnagramSolver(h);
}
  
permute(args[0]);
}



public static void permute( String input)
{
  System.out.println("Original/Input word is :" +input);
  int inputLength = input.length();
boolean[ ] used = new boolean[ inputLength ];
StringBuffer outputString = new StringBuffer();
char[ ] in = input.toCharArray( );
doPermute ( in, outputString, used, inputLength, 0 );
}

public static void doPermute ( char[ ] in, StringBuffer outputString,
boolean[ ] used, int inputLength, int level)
{
if( level == inputLength) {
String temp=solve(outputString.toString());
if(temp!=null)
{
System.out.println("");  
System.out.println("congratulations!!!! " +temp.toUpperCase()+" is the word in the dictionary");
  
System.exit(0);
}
return;
}

for( int i = 0; i < inputLength; ++i )
{   

if( used[i] ) continue;

outputString.append( in[i] );
used[i] = true;   
doPermute( in, outputString, used, inputLength, level + 1 );   
used[i] = false;   
outputString.setLength( outputString.length() - 1 );   
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.