word-ladder

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A transformation sequence from word <code>beginWord</code> to word <code>endWord</code> using a dictionary <code>wordList</code> is a sequence of words <code>beginWord -&gt; s1 -&gt; s2 -&gt; ... -&gt; sk</code> such that:

<ul>
	<li>Every adjacent pair of words differs by a single letter.</li>
	<li>Every <code>si</code> for <code>1 &lt;= i &lt;= k</code> is in <code>wordList</code>. Note that <code>beginWord</code> does not need to be in <code>wordList</code>.</li>
	<li><code>sk == endWord</code></li>
</ul>

Given two words, <code>beginWord</code> and <code>endWord</code>, and a dictionary <code>wordList</code>, return the number of words in the shortest transformation sequence from <code>beginWord</code> to <code>endWord</code>, or <code>0</code> if no such sequence exists.

&nbsp;
Example 1:

<pre>
Input: beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]
Output: 5
Explanation: One shortest transformation sequence is &quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;dot&quot; -&gt; &quot;dog&quot; -&gt; cog&quot;, which is 5 words long.
</pre>

Example 2:

<pre>
Input: beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;]
Output: 0
Explanation: The endWord &quot;cog&quot; is not in wordList, therefore there is no valid transformation sequence.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= beginWord.length &lt;= 10</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 &lt;= wordList.length &lt;= 5000</code></li>
	<li><code>wordList[i].length == beginWord.length</code></li>
	<li><code>beginWord</code>, <code>endWord</code>, and <code>wordList[i]</code> consist of lowercase English letters.</li>
	<li><code>beginWord != endWord</code></li>
	<li>All the words in <code>wordList</code> are unique.</li>
</ul>

ladderLength

Word Ladder

Word Ladder II

word-ladder-ii

单词接龙 II

Minimum Genetic Mutation

minimum-genetic-mutation

最小基因变化

Words Within Two Edits of Dictionary

words-within-two-edits-of-dictionary

距离字典两次编辑以内的单词

Breadth-First Search

Hash Table

String

字典&nbsp;<code>wordList</code> 中从单词 <code>beginWord</code>&nbsp;到&nbsp;<code>endWord</code> 的 转换序列 是一个按下述规格形成的序列<meta charset="UTF-8" />&nbsp;<code>beginWord -&gt; s1&nbsp;-&gt; s2&nbsp;-&gt; ... -&gt; sk</code>：

<ul>
	<li>每一对相邻的单词只差一个字母。</li>
	<li><meta charset="UTF-8" />&nbsp;对于&nbsp;<code>1 &lt;= i &lt;= k</code>&nbsp;时，每个<meta charset="UTF-8" />&nbsp;<code>si</code>&nbsp;都在<meta charset="UTF-8" />&nbsp;<code>wordList</code>&nbsp;中。注意， <code>beginWord</code>&nbsp;不需要在<meta charset="UTF-8" />&nbsp;<code>wordList</code>&nbsp;中。<meta charset="UTF-8" /></li>
	<li><code>sk&nbsp;== endWord</code></li>
</ul>

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

示例 1：

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

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= beginWord.length &lt;= 10</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 &lt;= wordList.length &lt;= 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> 中的所有字符串 互不相同</li>
</ul>