Word Ladder

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 transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

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

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

A:

这个算是经典的BFS题目吧？
------------------错误犯在 ： endWord 可能不在wordList里。 然而还能被reach到。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int n = beginWord.length();
        char arr[n+1];
        strcpy(arr, beginWord.c_str());
        set<string> myset;
        for(auto s:wordList)
            myset.insert(s);
        vector<string> vec;
        vec.push_back(beginWord);
        int res = 1;
        //bfs
        while(not vec.empty()) // for each BFS step, 
        {
            vector<string> newVec;
            res++;
            for(auto str : vec) // for each string at this distance
            {
                strcpy(arr, str.c_str());
                for(int i =0;i<n; ++i) // change at each position
                {
                    char oldCh = arr[i];
                    for(char ch = 'a';ch<='z';++ch)
                    {
                        if(ch == oldCh)
                            continue;
                        arr[i] = ch;
                        string tmp(arr);
                        if(myset.find(tmp) != myset.end())
                        {
                            if( tmp == endWord)
                                return res;
                            newVec.push_back(tmp);
                            myset.erase(tmp);
                        }
                    }
                    arr[i] = oldCh;
                }
            }            
            vec = newVec;
        }
        return 0;
    }
};

查看了网上一个，就是对每个字符，自己去对每个位置，做26个小写字母的变化 。再去dict里查找。（貌似查找比较快些）

Mistakes:
1: did not clearlly upderstand the problem,  actually, the start and end nodes are not in the dictionary.
( but could in the dicttionary, we should consider this case.)

2: start 的distance 应该设为 1

3： 又一次，华丽丽得，忘了update  pointer
                pointer = pointer.next;
4:  因为上面的原因， 哎， 就是， 对象不同。   导致了， 在adjacent  list中， 也是存入了不同的对象。  因此，其 distance value 都是MAX_VALUE 。  sigh~~~~~~~~
但，那样的话，压栈时加入V[i] 对象的引用。 但是， 在queue 的list中，由于也利用了 next value ，他的值，就变了呀？？？？？？？？？？？？？？？？
Solution：   给 graphNode 增加了一个新的值，叫做 adjList   （这样，graphNode 就有next 和 adjList 两个pointer。）

但是，这样，addAjacentNode()时， 还是要新生成Node变量。 否则总会循环的。

因为程序比较复杂（还有自己写的queue，graph， graphNode类）， 导致了addAjacent（）方法里，用了next（后来next设计给了queue用） 。 就耗时比较久。

4： 调试时，when find a vertex colored White, we enqueue it. But the queue is still empty.-----> enqueue() method does not work as expected.
调试发现，when Queue is empty, and we just add one item, tail is not null, but after we dequeue it. (now queue is empty. but we forget to make tail as null.)

5:  仔细读题，我们会发现 node hit 的d 已经是1 了。而不是我们通常所认为的0.

6: 已经在eclipse上通过了，可是，还是internal error. 打印语句也都注视掉了啊？？？？
------------------哦，注释掉打印语句的时候，多注释了一行if语句，导致大括号不匹配了。


7：因为hashSet不能一边遍历，一边删除。因此，我 开始的时候，用LinkedList来做删除。 可是，这样比较慢些（删除i位置，要先从头跑到这里）


Mistakes:
1：                chars[i] = oldCh;   忘了写。
2 : !!!!!!!!!!!!!!!!!   第二遍的时候， 写成了 每当从queue里poll出一个string，就在dict里删去。

但是， 从效率上来讲，应该是要加入queue的时候， 就从dict中删去。 这样更快一些！！
可是，从eclipse里看不出来， 反而前者更快。  但是， 不加入前从dict中删去的话，就通不过。 ╮(╯▽╰)╭


Learned:
1: 可以用LinkedList 来做 Queue的类。-------- 哎，你自己再定义一个， 挺SB的

2： LeetCode 不能用Hashtable,

3:  对于HashSet<String> dict
我们可以用
for(String str: dict)             当然，也可以用iterator


Mistakes:
for(char ch = 'a';ch<='z' && ch != origChar;ch++){

                   

上面这样写是不对的。会提早跳出来。