Leetcode: Word Ladder

题目:

https://oj.leetcode.com/problems/word-ladder/

分析:

  1. 求最短路径, 用BFS算法。 [3]

  2. 求各个单词之间的邻接关系, 不能用邻接矩阵, 否则会Time Limit Exceeded。 [2]

因为并非所有单词之间的邻接关系在求解过程中都需要, 只需要求解用到的一些单词的邻居即可。要是求邻接矩阵的话, 会花费大量时间。

  1. 一个单词访问过了之后, 直接从dict中删除即可, 从而避免重复加入队列,进而导致浪费时间。[1]

  2. 关于如何记录路径长, 可以再创建一个depth队列, 这样que队列push时, depth队列也同时的push一个对应的路径。[1]

代码:

class Solution
{
public:
    int ladderLength(string start, string end, unordered_set<string> &dict)
    {
        dict.insert(end);
        queue<string> que;
        queue<int> depth;
        que.push(start);
        depth.push(2);
        int len;

        while (!que.empty())
        {
            string ver = que.front();
            que.pop();
            len = depth.front();
            depth.pop();

            vector<string> res;
            adjacency(ver, dict, res);
            for (auto &r : res)
            {
                if (r == end)
                    return len;
                else
                {
                    dict.erase(r);
                    que.push(r);
                    depth.push(len+1);
                }
            }
        }

        return 0;
    };

    void adjacency(const string &ver, const unordered_set<string> &dict, vector<string> &res)
    {
        for (int i = 0; i < ver.size(); i++)
        {
            string temp = ver;
            for (int j = 'a'; j <= 'z'; j++)
            {
                temp[i] = j;
                if (temp != ver && dict.find(temp) != dict.end())
                    res.push_back(temp);
            }
        }

        return;
    }
};

参考:

[1] http://blog.csdn.net/lanxu_yy/article/details/17588317

[2] http://blog.csdn.net/yutianzuijin/article/details/12887747

[3] 《数据结构(C++语言版)》(第三版) 邓俊辉  p169

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38867667