Word Ladder

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

    Example

    Given:
    start = "hit"
    end = "cog"
    dict =

    As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
    return its length 5.

    Note

    • All words have the same length.
    • All words contain only lowercase alphabetic characters.
    1. start 和 end 相等。
    2. end 在 dict 中，且 start 可以转换为 dict 中的一个单词。
    3. end 不在 dict 中，但可由 start 或者 dict 中的一个单词转化而来。
    4. end 无法由 start 转化而来。

    由于中间结果也必须出现在词典中，故此题相当于图搜索问题，将 start, end, dict 中的单词看做图中的节点，节点与节点（单词与单词）可通过一步转化得到，可以转换得到的节点相当于边的两个节点，边的权重为1（都是通过1步转化）。到这里问题就比较明确了，相当于搜索从 start 到 end 两点间的最短距离，即 Dijkstra 最短路径算法。通过 BFS 和哈希表实现。

    首先将 start 入队，随后弹出该节点，比较其和 end 是否相同；再从 dict 中选出所有距离为1的单词入队，并将所有与当前节点距离为1且未访问过的节点（需要使用哈希表）入队，方便下一层遍历时使用，直至队列为空。

    的实现

    经验教训：根据给定数据结构特征选用合适的实现，遇到哈希表时多用其查找的 O(1) 特性。

    BFS 和哈希表的配合使用

    BFS 用作搜索，哈希表用于记录已经访问节点。在可以改变输入数据的前提下，需要将 end 加入 dict 中，否则对于不在 dict 中出现的 end 会有问题。