*Word Ladder II

本文主要是介绍*Word Ladder II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Return

  [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters.

分析：

class WordNode{String word;int numSteps;WordNode pre;public WordNode(String word, int numSteps, WordNode pre){this.word = word;this.numSteps = numSteps;this.pre = pre;}
}public class Solution {public List<List<String>> findLadders(String start, String end, Set<String> dict) {List<List<String>> result = new ArrayList<List<String>>();LinkedList<WordNode> queue = new LinkedList<WordNode>();queue.add(new WordNode(start, 1, null));dict.add(end);int minStep = 0;HashSet<String> visited = new HashSet<String>();  HashSet<String> unvisited = new HashSet<String>();  unvisited.addAll(dict);int preNumSteps = 0;while(!queue.isEmpty()){WordNode top = queue.remove();String word = top.word;int currNumSteps = top.numSteps;if(word.equals(end)){if(minStep == 0){minStep = top.numSteps;}if(top.numSteps == minStep && minStep !=0){//nothingArrayList<String> t = new ArrayList<String>();t.add(top.word);while(top.pre !=null){t.add(0, top.pre.word);top = top.pre;}result.add(t);continue;}}if(preNumSteps < currNumSteps){unvisited.removeAll(visited);}preNumSteps = currNumSteps;char[] arr = word.toCharArray();for(int i=0; i<arr.length; i++){for(char c='a'; c<='z'; c++){char temp = arr[i];if(arr[i]!=c){arr[i]=c;}String newWord = new String(arr);if(unvisited.contains(newWord)){queue.add(new WordNode(newWord, top.numSteps+1, top));visited.add(newWord);}arr[i]=temp;}}}return result;}
}

这篇关于*Word Ladder II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---