# 单词接龙

<p>字典 <code>wordList</code> 中从单词 <code>beginWord</code><em> </em>和 <code>endWord</code> 的 <strong>转换序列 </strong>是一个按下述规格形成的序列：</p>

<ul>
	<li>序列中第一个单词是 <code>beginWord</code> 。</li>
	<li>序列中最后一个单词是 <code>endWord</code> 。</li>
	<li>每次转换只能改变一个字母。</li>
	<li>转换过程中的中间单词必须是字典 <code>wordList</code> 中的单词。</li>
</ul>

<p>给你两个单词<em> </em><code>beginWord</code><em> </em>和 <code>endWord</code> 和一个字典 <code>wordList</code> ，找到从 <code>beginWord</code> 到 <code>endWord</code> 的 <strong>最短转换序列</strong> 中的 <strong>单词数目</strong> 。如果不存在这样的转换序列，返回 0。</p>
 

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

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
<strong>输出：</strong>5
<strong>解释：</strong>一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
</pre>

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

<pre>
<strong>输入：</strong>beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
<strong>输出：</strong>0
<strong>解释：</strong>endWord "cog" 不在字典中，所以无法进行转换。</pre>

<p> </p>

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

<ul>
	<li><code>1 <= beginWord.length <= 10</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>


## template

```java
public class Solution {

	HashMap<String, List<String>> mapPositive = new HashMap<String, List<String>>();
	HashMap<String, List<String>> mapNegative = new HashMap<String, List<String>>();
	HashMap<String, Boolean> mapVisit = new HashMap<String, Boolean>();

	int result = Integer.MAX_VALUE;

	public int ladderLength(String beginWord, String endWord, List<String> wordList) {

		for (int i = 0; i < wordList.size(); i++) {
			addWordToMap(wordList.get(i));
		}
		addWordToMap(beginWord);
		mapVisit.put(beginWord, true);
		findEnd(beginWord, endWord, 1);
		if (result == Integer.MAX_VALUE) {
			return 0;
		}
		return result;
	}

	private void addWordToMap(String word) {
		int length = word.length();
		if (length == 0) {
			return;
		}
		char[] chars = word.toCharArray();
		for (int i = 0; i < length; i++) {
			char now = chars[i];
			chars[i] = '*';
			String regex = new String(chars);
			List<String> list;

			if (mapPositive.containsKey(word)) {
				list = mapPositive.get(word);
			} else {
				list = new ArrayList<String>();
				mapPositive.put(word, list);
			}
			list.add(regex);

			if (mapNegative.containsKey(regex)) {
				list = mapNegative.get(regex);
			} else {
				list = new ArrayList<String>();
				mapNegative.put(regex, list);
			}
			list.add(word);

			chars[i] = now;
		}
		mapVisit.put(word, false);
	}

	private void findEnd(String nowWord, String endWord, int nowStep) {
		if (endWord.equals(nowWord)) {
			if (nowStep < result) {
				result = nowStep;
			}
			return;
		}
		List<String> candidates = getCandidates(nowWord);
		if (candidates == null || candidates.size() == 0) {
			return;
		}
		for (int i = 0; i < candidates.size(); i++) {
			String now = candidates.get(i);
			mapVisit.put(now, true);
			findEnd(now, endWord, nowStep + 1);
			mapVisit.put(now, false);
		}
	}

	private List<String> getCandidates(String word) {
		List<String> list = mapPositive.get(word);
		if (list == null) {
			return new ArrayList<String>();
		}
		Set<String> set = new HashSet<String>();
		for (int i = 0; i < list.size(); i++) {
			String regex = list.get(i);
			List<String> regexList = mapNegative.get(regex);
			if (regexList == null) {
				continue;
			}
			for (int j = 0; j < regexList.size(); j++) {
				String now = regexList.get(j);
				if (mapVisit.get(now) == false) {
					set.add(now);
				}
			}
		}
		List<String> candidates = new ArrayList<String>();
		for (String string : set) {
			candidates.add(string);
		}
		return candidates;
	}

}

```

## 答案

```java

```

## 选项

### A

```java

```

### B

```java

```

### C

```java

```