# 单词接龙 II

<p>按字典 <code>wordList</code> 完成从单词 <code>beginWord</code> 到单词 <code>endWord</code> 转化，一个表示此过程的 <strong>转换序列</strong> 是形式上像 <code>beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub></code> 这样的单词序列，并满足：</p>

<div class="original__bRMd">
<div>
<ul>
	<li>每对相邻的单词之间仅有单个字母不同。</li>
	<li>转换过程中的每个单词 <code>s<sub>i</sub></code>（<code>1 <= i <= k</code>）必须是字典 <code>wordList</code> 中的单词。注意，<code>beginWord</code> 不必是字典 <code>wordList</code> 中的单词。</li>
	<li><code>s<sub>k</sub> == endWord</code></li>
</ul>

<p>给你两个单词 <code>beginWord</code> 和 <code>endWord</code> ，以及一个字典 <code>wordList</code> 。请你找出并返回所有从 <code>beginWord</code> 到 <code>endWord</code> 的 <strong>最短转换序列</strong> ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表<em> </em><code>[beginWord, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>]</code> 的形式返回。</p>

<p> </p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
<strong>输出：</strong>[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
<strong>解释：</strong>存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
<strong>输出：</strong>[]
<strong>解释：</strong>endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>1 <= beginWord.length <= 7</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 <= wordList.length <= 5000</code></li>
	<li><code>wordList[i].length == beginWord.length</code></li>
	<li><code>beginWord</code>、<code>endWord</code> 和 <code>wordList[i]</code> 由小写英文字母组成</li>
	<li><code>beginWord != endWord</code></li>
	<li><code>wordList</code> 中的所有单词 <strong>互不相同</strong></li>
</ul>
</div>
</div>


## template

```java
class Solution {
	public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

		List<List<String>> res = new ArrayList<>();
		if (wordList == null)
			return res;

		Set<String> dicts = new HashSet<>(wordList);
		if (!dicts.contains(endWord))
			return res;
		if (dicts.contains(beginWord))
			dicts.remove(beginWord);

		Set<String> endList = new HashSet<>(),
				beginList = new HashSet<>();

		Map<String, List<String>> map = new HashMap<>();
		beginList.add(beginWord);
		endList.add(endWord);
		bfs(map, beginList, endList, beginWord, endWord, dicts, false);

		List<String> subList = new ArrayList<>();
		subList.add(beginWord);
		dfs(map, res, subList, beginWord, endWord);
		return res;
	}

	void dfs(Map<String, List<String>> map,
			List<List<String>> result, List<String> subList,
			String beginWord, String endWord) {
		if (beginWord.equals(endWord)) {
			result.add(new ArrayList<>(subList));
			return;
		}
		if (!map.containsKey(beginWord)) {
			return;
		}
		for (String word : map.get(beginWord)) {
			subList.add(word);
			dfs(map, result, subList, word, endWord);
			subList.remove(subList.size() - 1);
		}
	}

	void bfs(Map<String, List<String>> map, Set<String> beginList, Set<String> endList, String beginWord,
			String endWord, Set<String> wordList, boolean reverse) {
		if (beginList.size() == 0)
			return;
		wordList.removeAll(beginList);
		boolean finish = false;
		Set<String> temp = new HashSet<>();
		for (String str : beginList) {
			char[] charr = str.toCharArray();
			for (int chI = 0; chI < charr.length; chI++) {
				char old = charr[chI];
				for (char ch = 'a'; ch <= 'z'; ch++) {
					if (ch == old)
						continue;
					charr[chI] = ch;
					String newstr = new String(charr);
					if (!wordList.contains(newstr)) {
						continue;
					}

					if (endList.contains(newstr)) {
						finish = true;
					} else {
						temp.add(newstr);
					}

					String key = reverse ? newstr : str;
					String value = reverse ? str : newstr;
					if (!map.containsKey(key)) {
						map.put(key, new ArrayList<>());
					}
					map.get(key).add(value);

				}
				charr[chI] = old;
			}
		}
		if (!finish) {
			if (temp.size() > endList.size()) {
				bfs(map, endList, temp, beginWord, endWord, wordList, !reverse);
			} else {
				bfs(map, temp, endList, beginWord, endWord, wordList, reverse);
			}
		}
	}
}


```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```