LeetCode 127: Word Ladder

tags: String, BFS

---

Given two words(beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

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

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Function:

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    // Your Code
}

---

题目分析

该题目是一道基于String、LeetCode Medium的题目。显然可以用BFS算法求解：以beginWord为起点，以beginWord的下一跳为目标广度优先搜索wordList，并将符合条件的结果放入新的结果集中，然后对其进行新一轮的广度优先搜索，最终看是否能达到endWord。

下面会看到3个解法，分别是自己失败且丑陋的解法、常见的解法以及高效的解法。

算法1：自己的解法

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

    int result = 1;
    Set<String> wordListCopy = new HashSet<>(); // wordList的Clone，不影响原数据集的内容
    wordListCopy.addAll(wordList);
    wordListCopy.add(endWord);
    ArrayList<String> curAL = new ArrayList<>(); // BFS的队列
    curAL.add(beginWord);
    ArrayList<String> otherAL = new ArrayList<>(); // 存储新加入的元素
    Set<String> remove = new HashSet<>(); // 3.wordListCopy中应该删除的元素集合

    while (!curAL.contains(endWord)) {
        otherAL.clear();
        for (String temp : curAL) {
            for (String s : wordListCopy) { // 判断集合剩余的元素与队列元素是否相邻
                if (isNeighbor(temp, s)) { // 1.调用判断neighbor方法，TLE的关键
                    otherAL.add(s);
                    remove.add(s);
                }
            }
            remove.forEach(wordListCopy::remove); // 2.将新获取的元素在wordListCopy中删除
            remove.clear();
        }
        ArrayList<String> temp = curAL; // 4.我也不懂自己在做什么
        curAL = otherAL;
        otherAL = temp;
        result++; // 计算距离
        if (curAL.size() == 0)
            return 0;
    }
    return result;
}

public boolean isNeighbor(String s1, String s2) {
    int len = s1.length();
    char[] ch1 = s1.toCharArray();
    char[] ch2 = s2.toCharArray();
    int diff = 0;
    for (int i=0; i<len&&diff<2; i++) { // 逐个字符的判断两者的距离
        if (ch1[i]!=ch2[i]) {
            diff++;
        }
    }
    return diff <= 1;
}

虽然是几个月之前写的算法，但看上去还是那么亲切，真是热泪盈眶，简直丑爆了。根据严重程度，依次分析代码为什么TLE，为什么写得这么丑陋。

1. 判断相邻字符串是String类型的常见问题，开始看到他人代码中对字符串的每一个字符遍历26个字母感到不解，认为自己的isNeighbor方法效率会更高，然而在尝试将他人代码的该模块改成自己的isNeighbor时，TLE。经过仔细考虑，自己的想法太naive了：假设候选队列中有k个字符串，wordList剩有c个字符串，每个字符串的长度为l，字符遍历的复杂度为k*l*26，而自己方法的复杂度为k*c*l。很显然，后者比前者多了一个系数c，而且很可能c>>26，所以后者效率远不及前者，造成TLE。
2. 这一块的代码写得很丑陋，原因是开始我尝试在foreach循环中直接删除wordListCopy中被访问到的元素，但会抛出Concurrent ModificationException的异常。在当时编写代码时并不知道如何解决这个问题，所以改写的这么丑陋。最近复习Java集合的过程中找到了问题的根源：集合的迭代器在遍历过程中不允许修改集合信息，否则会抛出上述异常。下面两个算法都给出了相对优雅的解决方案。
3. remove集合其实和curAL保持实时一致，所以完全没必要申请这样一个集合做莫名其妙的记录。
4. 这个地方我也无力吐槽了。。。

算法2：常见的解法

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    Set<String> reached = new HashSet<>();
    reached.add(beginWord);
    wordList.add(endWord);
    int distance = 1;
    while(!reached.contains(endWord)) {
        Set<String> toAdd = new HashSet<>();
        for(String each : reached) {
            for (int i = 0; i < each.length(); i++) {
                char[] chars = each.toCharArray();
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    chars[i] = ch;
                    String word = new String(chars);
                    if(wordList.contains(word)) {
                        toAdd.add(word);
                        wordList.remove(word);
                    }
                }
            }
        }
        distance ++;
        if(toAdd.size() == 0) return 0;
        reached = toAdd;
    }
    return distance;
}

该解法是BFS算法的经典实现，简单优雅、略带粗暴。

1. 简单优雅：算法中使用2个集合实现了当前队列和候选队列，对相邻字符串的求解使用字符遍历的方法保证了效率，同时由于字符遍历的方法不需要wordList的迭代器，因此可以在循环中调用remove方法。
2. 略带粗暴：调用wordList的remove方法会对传入参数的内容产生修改，可能造成非预期的结果。算法3提供了另一种"删除元素的思路"。

算法3：高效的解法

public int wordLadder(String beginWord, String endWord, Set<String> wordList) {
    Set<String> beginSet = new HashSet<>();
    Set<String> endSet = new HashSet<>();

    int len = 1;
    HashSet<String> visited = new HashSet<>();

    beginSet.add(beginWord);
    endSet.add(endWord);
    while (!beginSet.isEmpty() && !endSet.isEmpty()) {
        if (beginSet.size() > endSet.size()) {
            Set<String> set = beginSet;
            beginSet = endSet;
            endSet = set;
        }

        Set<String> temp = new HashSet<>();
        for (String word : beginSet) {
            char[] chs = word.toCharArray();

            for (int i=0; i<chs.length; i++) {
                for (char c='a'; c<='z'; c++) {
                    char old = chs[i];
                    chs[i] = c;
                    String target = String.valueOf(chs);

                    if (endSet.contains(target)) {
                        return len + 1;
                    }

                    if (!visited.contains(target) && wordList.contains(target)) {
                        temp.add(target);
                        visited.add(target);
                    }
                    chs[i] = old;
                }
            }
        }
        beginSet = temp;
        len++;
    }
    return 0;
}

该解法的主要思想是从两端进行广度优先搜索，也即维护两个当前队列，每次遍历较小的队列，查找是否在另一个队列（找到路径）、是否在剩余的wordList中（形成新的候选队列）。虽然我不知道这种思路的效率有没有定理支持，但直观的感受是算法2中的思想类似于单点的水波需要扩很大才能到达目标点，而算法3在起点和终点都产生水波，这样可以扩较小的范围就碰到彼此，也即找到一条可达路径。假设wordList字符串的个数总共有n个，字符串的长度为l，则该算法的最坏情况就是遍历所有的字符串仍没有找到路径，此时的时间复杂度为O(n*l)，超过Java AC的90%。

总结

该题目难度不大，自己的实现却让人哭笑不得，需要从以下几点加强自己的编码训练：

• 字符串相关算法；
• 对常见算法——如BFS——的实现应倒背如流；
• 努力编写简单优雅的代码。