题目

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
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.

大意

给两个单词和一个字典，使用字典中有的单词，求从一个单词到另一个单词的最少的转换步骤。

答案

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
class Solution {
public:
    public:
        int ladderLength(string start, string end, vector<string> &dict) {
            vector<string>::iterator it=find(dict.begin(),dict.end(),end);
            if(it==dict.end()) return 0;//若字典里没有最终元素，直接返回0.
            return BFS(start,end,dict);
        };
    private:
        int BFS(string start,string end,vector<string> &dict1){
            unordered_set<string> dict(dict1.begin(),dict1.end());
            // 存放单词和单词所在层次
            queue<pair<string,int> > q;
            q.push(make_pair(start,1));
            unordered_set<string> visited;
            visited.insert(start);
            // 广搜
            bool found = false;
            while(!q.empty()){
                pair<string,int> cur = q.front();
                q.pop();
                string word = cur.first;
                int len = word.size();
                // 变换一位字符
                for(int i = 0;i < len;++i)
                {
                    string newWord(word);
                    for(int j = 0;j < 26;++j)
                    {
                        newWord[i] = 'a' + j;
                        if(newWord == end)
                        {
                            found = true;
                            return cur.second+1;
                        }
                        // 判断是否在字典中并且是否已经访问过
                        if(dict.count(newWord) > 0 && visited.count(newWord) == 0)
                        {
                            visited.insert(newWord);
                            q.push(make_pair(newWord,cur.second+1));
                        }
                    }
                }
            }//while
            if(!found){
                return 0;
            }//if
        };
};

思路

类似于leetcode279题，转换成图，然后对图使用BFS进行求解。

在set中存在某个元素可以用count函数>1来表示

vector判存在用find函数。