0127._Word_Ladde.md

127. Word Ladder

难度:Medium

刷题内容

原题连接

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

内容描述

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:

Only one letter can be changed at a time.
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:

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:

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

- 时间复杂度: O(EV+V^3)- 空间复杂度: O(n^2)******

这是一道不错的题，第一种用BFS解，首先我们构造一个图，用二维数组储存，然后BFS一层一层搜索。上面E是边的数量，v是节点的数量

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        int len = wordList[0].length(),length = wordList.size();
        queue<int> q;
        vector<int> d[length];
        int min_l[length];
        for(int i = 0;i < length;++i)
            min_l[i] = INT_MAX;
        for(int i = 0;i < length;++i)
            for(int j = i + 1;j <length;++j)
            {
                int count1 = 0;
                for(int t = 0;t < len;++t)
                    if(wordList[i][t] != wordList[j][t])
                        count1++;
                if(count1 == 1)
                {
                    d[i].push_back(j);
                    d[j].push_back(i);
                }
            }
        int exit = -1;
        for(int i = 0;i < length;++i)
            if(wordList[i] == endWord)
            {
                exit = i;
                min_l[i] = 0;
                q.push(i);
            }
        if(exit == -1)
            return 0;
        while(q.size())
        {
            int t = q.front();
            for(int i = 0;i < d[t].size();++i)
                if(min_l[d[t][i]] > min_l[t] + 1)
                {
                    q.push(d[t][i]);
                    min_l[d[t][i]] = min_l[t] + 1;
                    if(d[t][i] == length - 1)
                        return min_l[length - 1] + 1;
                }
            q.pop();
        }
        return 0;
    }
};

思路2

- 时间复杂度: O(EVlen)- 空间复杂度: O(V)*****

上面的方法效率不高，因此可以改用用unordered_set储存所有的字符串，然后每次只改动一个字符，在set中查找这个单词是否存在即可。上面的len是每个单词的长度。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        wordList.push_back(beginWord);
        int len = wordList[0].length(),length = wordList.size();
        queue<string> q;
        unordered_set<string> s(wordList.begin(),wordList.end());
        int min_l[length];
        auto pos = s.find(endWord);
        if(pos == s.end())
            return 0;
        q.push(*pos);
        int level = 1;
        string count1 = endWord;
        while(q.size())
        {
            string temp1 = q.front();
            for(int j = 0;j < temp1.size();++j)
            {
                string temp = temp1;           
                for(int i = 'a';i <= 'z';++i)
                {
                    temp[j] = i;
                    if(temp != temp1 && s.find(temp) != s.end())
                    {
                        q.push(temp);
                        if(temp == beginWord)
                            return level + 1;
                        s.erase(temp);
                    }
                    temp = temp1;
                }
            }
            if(count1 == temp1)
            {
                count1 = q.back();
                level++;
            }
            s.erase(temp1);
            q.pop();
        }
        return 0;
    }
};