127. 单词接龙

Problem: 127. 单词接龙

思路

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。很显然这道题目可以用双向广搜来解决。

解题方法

将开始字符添加到小的一侧（set），将结束字符添加到大的一侧（set）。
从小的一侧开始拓展，暴力展开，如果大的一侧中有与当前字符相同的就说明找到了，两侧连通起来的，返回当前的len即可，每变换一次在总的字典中寻找如果存在，删除记录防止重复也就是剪枝。交换的过程：如果当前层小于等于较大层，交换当前层和较小层，反之，当前层大于较大层，交换当前层和较大层，较大层和较小层

复杂度

时间复杂度:

时间复杂度方面，由于我们同时从两个方向进行搜索，所以时间复杂度会相对较低。具体的时间复杂度取决于搜索的层数，最坏情况下为

O

(

M

∗

N

2

)

O(M*N^2)

O(M∗N2)，其中M为wordList的长度，N为单词的平均长度。

空间复杂度:

空间复杂度方面，我们使用了三个集合smallLevel、bigLevel和nextLevel来存储单词，以及一个HashSet来存储总词汇表。所以空间复杂度为

O

(

M

)

O(M)

O(M)，其中M为wordList的长度。

Code

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        // 总词汇表
        Set dict = new HashSet(wordList);
        if (!dict.cont服务器托管网ains(endWord)) {
            return 0;
        }
        // 数据量小的一侧
        Set smallLevel = new HashSet();
        // 数据量大的一侧
        Set bigLevel = new HashSet();
        // 数据量小的下一侧
        服务器托管网Set nextLevel = new HashSet();
        smallLevel.add(beginWord);
        bigLevel.add(endWord);
        for (int len = 2; !smallLevel.isEmpty(); len++) {
            for (String w : smallLevel) {
                // 从小的一侧拓展
                char[] word = w.toCharArray();
                for (int j = 0; j  temp = smallLevel;
                smallLevel = nextLevel;
                nextLevel = temp;
            } else {
                // 当前层大于较大层 交换当前层和较大层 较大层和较小层
                Set temp = smallLevel;
                smallLevel = bigLevel;
                bigLevel = nextLevel;
                nextLevel = temp;
            }
            nextLevel.clear();
        }
        return 0;
    }
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net