# Java: String Permutation, Breadth/Depth Searching

**URL:** <https://forum.kirupa.com/t/java-string-permutation-breadth-depth-searching/206270>\
**Category:** web dev\
**Created:** [November 6, 2006, 6:41pm UTC](https://forum.kirupa.com/t/java-string-permutation-breadth-depth-searching/206270 "2006-11-06T18:41:52Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [November 6, 2006, 6:41pm UTC](https://forum.kirupa.com/t/java-string-permutation-breadth-depth-searching/206270/1 "2006-11-06T18:41:52Z")

</div>

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.

```auto
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:
";
        for ( String word: dict.keySet() ) {
            output += word + "
";
            for ( String connected: dict.get(word) ) {
                output += "	" + connected + "
";
            }
        }
        output += "

Path:
";
        for ( String word: path ) {
            output += word + "
";
        }
        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,

```auto
12
care
cart
cure
dare
dart
hare
here
hire
sire
sure
were
wire

```

What am I missing?