LeetCode: 127. 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.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

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.

题目大意： 题目类似于 LeetCode: 126. Word Ladder II。根据给定的开始结束单词以及字母表，求出从开始单词到结束单词的最短路径的长度。要求路径上的每个单词之间只有一个字母之差。

解题思路 —— 广度优先搜索(BFS)

广搜，记录步数，当第一次搜索到 endWord 时的步数就是最短路径的长度。

AC 代码

class Solution {
private:
    // 判断两个单词是否只相差一个字母
    bool isNear(string lhv, string rhv)
    {
        if(lhv.size() != rhv.size()) return false;

        int cnt = 0;
        for(int i = 0; i < lhv.size() && cnt < 2; ++i)
        {
            if(lhv[i] != rhv[i])
            {
                ++cnt;
            }
        }

        return (cnt == 1);
    }    
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
         multimap<string, string> wordDir; //wordDir[i] = j 表示 i 到 j 只有一个字母不同

        // 计算距离，将相邻的节点存入 wordDir 中
        for(int i = 0; i < wordList.size(); ++i)
        {
            for(int j = i+1; j < wordList.size(); ++j)
            {
                if(isNear(wordList[i], wordList[j]))
                {
                    wordDir.insert({wordList[i], wordList[j]});
                    wordDir.insert({wordList[j], wordList[i]});
                }
            }
        }

        // Each transformed word must exist in the word list. 
        // Note that beginWord is not a transformed word.
        if(wordDir.find(beginWord) == wordDir.end())
        {
            for(int i = 0; i < wordList.size(); ++i)
            {
                if(isNear(wordList[i], beginWord))
                {
                    wordDir.insert({wordList[i], beginWord});
                    wordDir.insert({beginWord, wordList[i]});
                }
            }
        }

         // 计算最短路径
        queue<string> que;
        unordered_set<string> flags;

        // 初始化...
        // 用 ‘#’ 分割开搜索的每一层字符串
        que.push(beginWord);
        que.push("#");
        flags.insert(beginWord);
        int stepNum = 0;
        int minStepNum = 0;

        // 计算最短路径 
        while(!que.empty())
        {
            string curWord = que.front();
            que.pop();

            if(curWord == "#") 
            {
                ++stepNum;
                if(!que.empty()) que.push("#");
                continue;
            }
            if(curWord == endWord) 
            {
                minStepNum = ++stepNum;
                break;
            }

            for(auto iter = wordDir.find(curWord);
                  iter != wordDir.end() && iter->first == curWord; ++iter)
            {
                if(flags.find(iter->second) == flags.end())
                {
                    flags.insert(iter->second);
                    que.push(iter->second);
                }
            }
        }

        return minStepNum;
    }
};