Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
- Only one letter can be changed at a time
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return an empty list if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Example 2:
Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.-----------------
在I上做了一些修改，每个Pair都会记录当前走过的点
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
int n = beginWord.length();
Map<String, Integer> dic = getDic(wordList);
dic.put(beginWord, 1);
Queue<Pair> que = new LinkedList<>();
List<String> ll = new ArrayList<>();
ll.add(beginWord);
que.add(new Pair(1, beginWord, ll));
List<List<String>> rt = new ArrayList<>();
while (!que.isEmpty()) {
Pair p = que.poll();
String cur = p.s;
if (!rt.isEmpty() && p.level > rt.get(0).size()) {
return rt;
}
if (cur.equals(endWord)) {
rt.add(p.list);
continue;
}
for (int i = 0; i < n; i++) {
char c = cur.charAt(i);
for (char nextC = 'a'; nextC <= 'z'; nextC++) {
String next = cur.substring(0, i) + nextC + cur.substring(i + 1);
// Note: ">=", as we want to output all possible paths.
if (dic.containsKey(next) && dic.get(next) >= p.level + 1) {
List<String> l = new ArrayList<>(p.list);
l.add(next);
que.add(new Pair(p.level + 1, next, l));
dic.put(next, p.level + 1);
}
}
}
}
return rt;
}
private Map<String, Integer> getDic(List<String> wordList) {
Map<String, Integer> dic = new HashMap<>();
for (String s : wordList) {
dic.put(s, Integer.MAX_VALUE);
}
return dic;
}
class Pair{
public int level;
public String s;
public List<String> list;
public Pair(int level, String s, List<String> list) {
this.level = level;
this.s = s;
this.list = list;
}
}
}
