lintcode 单词接龙

Posted on | In

描述

给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。

变换规则如下：

每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)

样例

1

输入：start = “a”，end = “c”，dict =[“a”,”b”,”c”]
输出：2
解释：
“a”->”c”

2

输入：start =”hit”，end = “cog”，dict =[“hot”,”dot”,”dog”,”lot”,”log”]
输出：5
解释：
“hit”->”hot”->”dot”->”dog”->”cog”

注意事项

如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

思路

bfs
使用一个队列，把和start距离为n的依次放入，每次遍历队列中所有元素，如果和end距离为1则可以返回，否则将距离为n+1的放入。
循环条件为队列不为空，如果为空，说明没有这样的转换序列，返回0

问题

使用unodered_set遍历时一直出现溢出报错 于是换成了vector，此问题先放着

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    int distance(const string &a, const string &b) {
        int res = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a[i] != b[i])
                res++;
        }
        return res;
    }

    int ladderLength(string &start, string &end, unordered_set<string> dict) {
        // write your code here
        if (distance(start, end) == 1) return 2;

        vector<string> v;
        for (string s : dict)
            v.push_back(s);

        queue<string> q;
        q.push(start);
        for (vector<string>::iterator it = v.begin(); it != v.end(); ) {
            if (*it == start)
                v.erase(it);
            else
                ++it;
        }

        int res = 2;
        while(!q.empty()){
            int n = q.size();
            for (int i = 0; i < n; i++) {

                string temp = q.front();
                q.pop();
                if (distance(temp, end) == 1)
                    return res;

                for (vector<string>::iterator it = v.begin(); it != v.end();) {
                    if (distance(temp, *it)==1) {
                        q.push(*it);
                        v.erase(it);
                    }
                    else
                        ++it;
                }

            }
            res++;

        }
        return 0;

    }
};
-------------end of filethanks for reading-------------