ORID27

[127] Word Ladder解题报告

BFS算法

用什么算法?
这道题需要用 BFS
为什么用这个算法（那些条件）
我是按照标签来找到这道题的，由于BFS的题性价比高，所以优先练习BFS的题目
这道题我按照自己的思路写了一个答案，但是始终有情况过不了关。所以去看别人的答案
我自己的思想就还是按照Queue这个数据结构来实现，把他给的wordlist从第一个放到队列里去，然后看它和给的beginword是否相等或者差一个char，如果这样就step++（把需要多少步找到endword记住）， 然后把s设定为当前的word，继续寻找队列里的word。知道找到endword为止，找到的时候就return step。
只是我好像代码里哪里出了问题，在这个情况里给的是3而答案却是2
Wrong Answer:
input:"a"
"c"
["a","b","c"]
Output:3
Expected:2
因为a先转化成b，然后c。这需要两步，我改了代码之后还是有一个case过不去，想了半天没找到问题在哪，我觉得可能是我验证当前string能否转化成wordlist里面的一个string的方式有问题吧。
最后看到一个答案比较好理解。

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        HashSet<String> wordSet = new HashSet<>(wordList);
        wordSet.remove(beginWord); // the same as marking visited
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size(); step++;
            while (size-- > 0) {
                String str = q.poll();
                if (str.equals(endWord)) return step; // found shortest transformation path
                for (int i = 0; i < str.length(); i++) {
                    char[] chars = str.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) { // try to change 1 character of `str`
                        chars[i] = c;
                        String newStr = new String(chars);
                        if (wordSet.contains(newStr)) {
                            q.offer(newStr);
                            wordSet.remove(newStr); // the same as marking visited
                        }
                    }
                }
            }
        }
        return 0; // no such transformation sequence.
    }

他的思路跟我差不多，先建立一个queue，然后把begin word放到里面。在此同时建立一个hashset，这就是为了方便寻找有没有可以转换的string，而他remove beginword这一行很亮，因为这就不会导致答案多一个的情况，也就是我上面提到出现的问题，比如beginWord = "a", endWord = "c". wordList = [a,b,c]。 他在remove beginWord的时候就已经让wordlist变成了[b,c] ，这样就不会多出一个了。
初始设置为0是想保证你进入循环之前step是0步。
其实就是说如果beginWord如果没有，那就返回0。
进入第一个while就是先把queue的size保存，然后把当前一层的queue循环一边，就是说如果有跟当前string只差一个char的string，它都会把它丢到queue里面，然后再循环，如果找到了根endword一摸一样的string，直接return step，如果没有，继续寻找，知道wordlist为空（他中间在不断remove wordlist里面的词）

值得记住的地方

                for (int i = 0; i < str.length(); i++) {
                    char[] chars = str.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) { // try to change 1 character of `str`
                        chars[i] = c;
                        String newStr = new String(chars);
                        if (wordSet.contains(newStr)) {
                            q.offer(newStr);
                            wordSet.remove(newStr); // the same as marking visited
                        }

其实这一段代码我一开始没看懂，因为不知道for (char c ='a'; c <= 'z'; c++ )这个循环是用来干什么的，后来自己放到IDE里面试了一下，发现实际上他就是把string.toCharArray() 这个char[] 每个字母都尝试变换了一下，因为在这个for loop里面，每个c都从‘a'到 'z'循环了一遍，而且这个string 每个位置都尝试了一次，然后去跟wordset里面的词对比，如果有，就证明你可以通过改变当前单词的一个字母来转换到wordset里面的一个单词。所以可以加入到queue里面。
举个例子
如果当前单词是"string", 那么string.toCharArray() 这个method实际上就把它变成了[s,t,r,i,n,g]，然后for （char c = 'a'; c<='z'; c++) 这里面会把chars[i] 从a到z都试一遍。for example, "atring","btring", "ctring","dtring" etc。 然后对比wordset里面有没有这个词。假如你wordset里面是"strkng","strhng"这两个词，你end word是strhng。那么你只能在i=3的时候循环到这个位置，并保存到queue 里面，这个queue是你改变一个字母能够变成的单词，所以每一次queue的循环都是一次改变。
如果当前queue里面有endword，return step。这逻辑没问题！

代码实现

有什么要注意的地方

有什么可以优化的地方

时空复杂度分析

...

相关题目有哪些做过的

跟哪个题目比较像？