127. Word Ladder

发表于 | 分类于

每日一题 2019 - 05 - 01

题目：

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.

解法：

这个题给出开始与结束的两个长度相同的字符串，让找出从开始到结束包含在 wordlist 中的所有字符串组合，简单来说就是宽度优先搜索，从 beginword 开始进行搜索，对每一个待搜索单词进行挨个字符的递增变换，如果存在于 wordlist 中就加入到待查序列中，直到 wordlist 被查找完毕或者待查序列为空；

代码：

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
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        map<string,int> now ;
        map<string,int> re ;
        for(int i = 0 ; i < wordList.size() ; i ++)
        {
            now[wordList[i]] = 1 ;
        }
        queue<string> q ;
        q.push(beginWord);
        re[beginWord] = 1 ;
        while( (!q.empty()) && now.size())
        {
            string temp = q.front();
            q.pop();
            int num = re[temp];
            int len = temp.size() ;
            for(int i = 0 ; i < temp.size() ; i ++ )
            {
                string tmp = temp ;
                for(char change = 'a' ; change <= 'z' ; change ++ )
                {
                    if(tmp[i] == change)
                    {
                        continue;
                    }
                    else
                    {
                        tmp[i] = change ;
                    }
                    if(now.find(tmp) != now.end())
                    {
                        if(tmp == endWord)
                        {
                            return num + 1 ;
                        }
                        q.push(tmp);
                        re[tmp] = num + 1 ;
                        now.erase(tmp);
                    }
                }
            }
        }
        return 0 ;
    }
};
0%
undefined