推荐订阅源

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

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

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

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

Note:

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

第二题是

进一步输出所有的路径。

第一题：

这个题目，直观的解法是BFS，1层1层的搜

当某一层的的节点中出现了end 节点就算找到了。

搞两个queue，一个是当前queue，一个nextqueue

1. 在遍历当前queue的时候，判断节点是不是end, 如果是，那就找了了，对应的层数就是长度

2.在遍历的时候，把所有的1edit 字典词统统放到那个nextqueue里面去。

3.当当前queue变空的时候，把两个queue交换。当前queue变成nextqueue, nextqueue变成currentqueue

代码实现

  int ladderLength(string start, string end, unordered_set<string> &dict) {
      if (start.length() != end.length()) return 0;
        unordered_set<string> path;
        queue<string> currentqueue;
        queue<string>nextqueue;
        unordered_set<string> usedstring;
        currentqueue.push(start);
        usedstring.insert(start);
        string word;
        int depth = 0;

        while (!currentqueue.empty())
        {
            word = currentqueue.front();
            currentqueue.pop();
            if (word == end){
                depth += 1;
                break;
            }
    
            for (int i = 0; i < word.length(); i++)
            {
                string candidate = word;
                for (int k = 0; k < 26; k++)
                {
                    candidate[i] = 'a' + k;
                    if (dict.find(candidate) != dict.end() && usedstring.find(candidate) == usedstring.end())
                    {
                        nextqueue.push(candidate);
                        usedstring.insert(candidate);
                    }    
                }
            }
    
            if (currentqueue.empty() && !nextqueue.empty())
            {
                depth++;
                currentqueue = nextqueue;
                while (!nextqueue.empty())
                    nextqueue.pop();
            }
        }
        return depth;
    }

第二题

直观了来讲，第二题注意两点：

1. 在找到第一个最短路径的时候，不能直接停止，要等到整个当前queue全部遍历完后在结束

2. 上面的算法中只考虑了层数的问题，没有记下路径问题。

简单的解决方案，改变节点，把节点弄成 

Node {

string str;

Node* parent;

}

那么找到这个节点之后往后回溯也能搞定

vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {

    bool canbreak = false;
    bool onthepath = false;
    queue<Node*> currentqueue;
    queue<Node*>nextqueue;
    vector<vector<string>> result;
    unordered_set<string> usedstring;
    dict.insert(end);
    Node node(start);
    node.parent = NULL;

    currentqueue.push(&node);
    string word;

    if (start.length() != end.length()) return result;
    while (!currentqueue.empty())
    {
        Node* m_node = currentqueue.front();
        word = m_node->str;
        currentqueue.pop();
        usedstring.insert(word);

        if (word == end){   //找到了那就遍历一边把结果输出。然后告诉这层遍历完就可以结束了
            vector<string> path;
            while (m_node->parent != NULL)
            {
                path.push_back(m_node->str);
                m_node = m_node->parent;
            }
            path.push_back(m_node->str);
            reverse(path.begin(), path.end());
            result.push_back(path);
            canbreak = true;
            continue;
        }

        if (!canbreak)
        {
            for (int i = 0; i < word.length(); i++)
            {
                string candidate = word;

                for (int k = 0; k < 26; k++)
                {
                    onthepath = false;
                    candidate[i] = 'a' + k;
                    if (dict.count(candidate) > 0 && usedstring.count(candidate)==0)
                    {
                        Node* tmp = new Node(candidate);
                        tmp->parent = m_node;
                        nextqueue.push(tmp);
                    }
                }
            }

            if (currentqueue.empty() && !nextqueue.empty())
            {
                currentqueue = nextqueue;    //交换queue
                while (!nextqueue.empty())   //queue没有clear函数
                    nextqueue.pop();
            }
        }
    }
    return result;

}

这个方法也work，

但是报空间和时间用的太多了。。。。

Time Limit Exceeded

所以得寻早更好的办法，

更快，更加省空间。

回忆前面做过的wordbreak II的例子。

catsanddog

0

1     c   NULL

2     a   NULL

3     t     0

4     s    0

5     a    NULL

6     n    NULL

7     d    3,4 

8     d   NULL

9     o   NULL

10   g    7

这个思路也可以用在这个地方

对整个dict建从start开始的查找表

比如 "hot", "cog", "dog", "tot", "hog", "hop", "pot", "dot" 

start hot

end dog

从start开始建表

1 hot   --->NULL

2 cog   --->hog(2)

3 dog----->dot(2), hog(2)

4 tot------>hot (1)

5 hog ----->hot(1)

6 hop------>hot(1)

7 pot------>hot(1)

8 dot------>hot(1)

从hot->dog 需要 hot->dot->dog or hot ->hog->dog

depth是3

这个lookup table是从start开始build的。

代码

void GeneratePath(unordered_map<string, vector<string>> &lookup, vector<string>& path, string& word, vector<vector<string>>& result)
    {
        if (lookup[word].size() == 0)
        {
            path.push_back(word);
            vector<string> curPath = path;
            reverse(curPath.begin(), curPath.end());
            result.push_back(curPath);
            path.pop_back();
            return;
        }
    
        path.push_back(word);
        for (auto iter = lookup[word].begin(); iter != lookup[word].end(); ++iter)
        {
            GeneratePath(lookup, path, *iter, result);
        }
        path.pop_back();
    }
    
    vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict)
    {
        vector<vector<string>> result;
        result.clear();
        unordered_map<string, vector<string>> lookup;
        unordered_set<string> usedwords;
        
        for (auto iter = dict.begin(); iter != dict.end(); ++iter)
        {
            lookup[*iter] = vector<string>();
        }
    
        vector<unordered_set<string>> workqueue(2);
    
        int current = 0;
        int previous = 1;
    
        workqueue[current].insert(start);
    
        while (true)
        {
            current = !current;       //两个队列的作用互换
            previous = !previous;     //
    
            for (auto iter = workqueue[previous].begin(); iter != workqueue[previous].end(); ++iter) 
            {
                usedwords.insert(*iter); //把前面那个队列里面的用过的字符串加到用过的里面。    
            }
    
            workqueue[current].clear();
    
            for (auto iter = workqueue[previous].begin(); iter != workqueue[previous].end(); ++iter) //遍历当前depth的层
            {
                for (size_t pos = 0; pos < iter->size(); ++pos)
                {
                    string candidate = *iter;
                    for (int i = 'a'; i <= 'z'; ++i)
                    {
                        if (candidate[pos] == i)
                        {
                            continue;
                        }
    
                        candidate[pos] = i;
    
                        if (dict.count(candidate) > 0 && usedwords.count(candidate) == 0)    //看看字典里有没有，而且这个词是不是已经用过了
                        {
                            lookup[candidate].push_back(*iter);                              //更新查找表
                            workqueue[current].insert(candidate);                            //插到nextqueue里面去
                        }
                    }
                }
            }
    
            if (workqueue[current].size() == 0)  //当前queue所有的子节点都不在字典里，那就找完了。没有             
            {
                return result;
            }
            if (workqueue[current].count(end))  //在当前层的队列中，有这个end节点，那就可以结束了。后面要做的就是根据回溯来建路径
            {
                break;
            }
        }
    
        vector<string> path;
        GeneratePath(lookup, path, end, result);
    
        return result;
    }

这个算法和图中的BFS非常类似

找的过程就是建图的过程。