Jeff Wheeler
November 6th, 2006, 02:41 PM
Ok, it's not often I post a question here, but I'm stumped by this easy problem.
I need to write a Java app which can find the shortest path between two words, changing only one letter at a time, using a given dictionary.
My teacher's stuff says to use recursion, which would be a depth-based algorithm; I think I need to use a breadth-based search algorithm instead, however, because it's looking for the shortest path.
package Lab09;
import java.io.*;
import java.util.*;
class Permutation {
HashMap<String, HashSet<String>> dict; // Contain set of similar words
TreeSet<String> path; // Order matters!
Permutation ( ) {
dict = new HashMap<String, HashSet<String>>();
path = new TreeSet<String>();
}
public void addToDict ( String word ) {
dict.put(word, new HashSet<String>());
for ( String potentiallySimilar: dict.keySet() ) {
// Add both direction connections
if ( isSimilar(word, potentiallySimilar)
&& !word.equals(potentiallySimilar) ) {
dict.get(word).add(potentiallySimilar);
if ( dict.containsKey(potentiallySimilar) ) {
dict.get(potentiallySimilar).add(word);
}
}
}
}
public void permutation ( String start, String target ) {
TreeSet<String> path = new TreeSet<String>();
path.add(start);
permutation(target, path);
}
/*
public void permutation ( String target, ) {
// Validate we're not already there
for ()
}
*/
public boolean isSimilar ( String first, String second ) {
if ( first.length() == second.length() ) {
int difference = 0;
for ( int i = 0; i < first.length(); i++ ) {
if ( first.charAt(i) != second.charAt(i) ) {
difference++;
}
}
return (difference <= 1);
} else {
return false;
}
}
public String toString ( ) {
String output = "Dict:\n";
for ( String word: dict.keySet() ) {
output += word + "\n";
for ( String connected: dict.get(word) ) {
output += "\t" + connected + "\n";
}
}
output += "\n\nPath:\n";
for ( String word: path ) {
output += word + "\n";
}
return output;
}
}
public class Lab09f {
public static void main ( String[] args ) throws IOException {
// Create new permutation object
Permutation permutation = new Permutation();
Scanner file = new Scanner(new File("Files/lab09f.dat"));
file.nextLine(); // Who cares about the number of following lines?
while ( file.hasNext() ) {
permutation.addToDict(file.next());
}
permutation.permutation("care", "wire");
System.out.println(permutation);
}
}
lab09f.dat contains,
12
care
cart
cure
dare
dart
hare
here
hire
sire
sure
were
wire
What am I missing?
I need to write a Java app which can find the shortest path between two words, changing only one letter at a time, using a given dictionary.
My teacher's stuff says to use recursion, which would be a depth-based algorithm; I think I need to use a breadth-based search algorithm instead, however, because it's looking for the shortest path.
package Lab09;
import java.io.*;
import java.util.*;
class Permutation {
HashMap<String, HashSet<String>> dict; // Contain set of similar words
TreeSet<String> path; // Order matters!
Permutation ( ) {
dict = new HashMap<String, HashSet<String>>();
path = new TreeSet<String>();
}
public void addToDict ( String word ) {
dict.put(word, new HashSet<String>());
for ( String potentiallySimilar: dict.keySet() ) {
// Add both direction connections
if ( isSimilar(word, potentiallySimilar)
&& !word.equals(potentiallySimilar) ) {
dict.get(word).add(potentiallySimilar);
if ( dict.containsKey(potentiallySimilar) ) {
dict.get(potentiallySimilar).add(word);
}
}
}
}
public void permutation ( String start, String target ) {
TreeSet<String> path = new TreeSet<String>();
path.add(start);
permutation(target, path);
}
/*
public void permutation ( String target, ) {
// Validate we're not already there
for ()
}
*/
public boolean isSimilar ( String first, String second ) {
if ( first.length() == second.length() ) {
int difference = 0;
for ( int i = 0; i < first.length(); i++ ) {
if ( first.charAt(i) != second.charAt(i) ) {
difference++;
}
}
return (difference <= 1);
} else {
return false;
}
}
public String toString ( ) {
String output = "Dict:\n";
for ( String word: dict.keySet() ) {
output += word + "\n";
for ( String connected: dict.get(word) ) {
output += "\t" + connected + "\n";
}
}
output += "\n\nPath:\n";
for ( String word: path ) {
output += word + "\n";
}
return output;
}
}
public class Lab09f {
public static void main ( String[] args ) throws IOException {
// Create new permutation object
Permutation permutation = new Permutation();
Scanner file = new Scanner(new File("Files/lab09f.dat"));
file.nextLine(); // Who cares about the number of following lines?
while ( file.hasNext() ) {
permutation.addToDict(file.next());
}
permutation.permutation("care", "wire");
System.out.println(permutation);
}
}
lab09f.dat contains,
12
care
cart
cure
dare
dart
hare
here
hire
sire
sure
were
wire
What am I missing?