Create a Graph of words who differ by 1 char

I have a Map which contains a

• key = length of words
• value = arraylist with words of that length

an example of the map:

• [1] = a, [2] = at, in, it, an, ...

1.User will input wordA

2.User 开发者_运维百科will input wordB

3.Will check if both the same length

4.If yes, a graph will be made with all the words that differ from wordA by 1 letter being adjacent.

5.Then those words that differ from wordA by one letter will be adjacent to words that differ from them by 1 letter. This is done until wordB is reached.

How can I make the graph and adjacency list?

What can I use to find the path from word1 to word2.

Thank you, Fernando Diaz

In terms of building the path from word1 to word2, this should give you something to start with:

    public static List<String> findLadder(String word1, String word2) {
        //invalid request
        if (word1 == null || word2 == null || word1.length() != word2.length()) {
            return Collections.emptyList();
        }

        List<String> result = new ArrayList<String>();
        List<String> words = dictionary.get(word1.length());
        result.add(word1);

        while (! word1.equals(word2)) {
            String nextWord = null;
            for (int index = 0; index < word1.length(); index++) {
                if (word1.charAt(index) != word2.charAt(index)) {
                    String testWord = word1.substring(0, index) + word2.charAt(index) + word1.substring(index + 1);
                    if (words.contains(testWord)) { 
                        nextWord = testWord;
                        word1 = nextWord;
                        result.add(word1);
                        break;
                    }
                }
            }
            if (nextWord == null) {
                //no mapping exists
                return Collections.emptyList();
            }
        }

        return result;
    }

Note that this code will not evaluate any moves that don't move incrementally closer to the desired output, such as code -> core when mapping from "code" to "data". Evaluation of such moves is for you to figure out.

Example here: http://ideone.com/9JnNH