CPP解决方案中的字梯解释

给定一个begin_word和end_word，找到从begin_word转换为end_word的单词。

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As 上 e shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

这个问题可以通过两种方式解决。

1. BFS
2. 2端BFS

3. 使用常规BFS解决：

因此，问题为我们提供了起始词和结束词，以及一个词典。此处的目标是通过一次仅更改一个字母来查看是否存在从开始单词到结束单词的方法。

一种简单的方法是遍历所有情况的蛮力方法。

如果以我们的示例为例，起始词是“ hit”，则从起始字母“ ait”，“ bit”，“ cit”…“ yit”，“ zit”开始替换，如果词典中存在任何词，则保存这个词。当达到“热”时，我们将其保存，然后再次从第一个字符“ cot”，“ dot”开始，现在也存在“ dot”，将其保存。

因此，我们使用BFS代替DFS，因为BFS确保了最短的路径。

2. 使用2端BFS求解。

在此解决方案中，我们同时从起始词和结束词开始路径，并在中间合并。

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<queue>

using namespace std;

int ladderLength_bfs(string beginWord, string endWord, vector<string>& wordList) 
{
	unordered_set<string> wordSet(wordList.begin(), wordList.end());
	unordered_map<string, int> pathCnt{{{beginWord, 1}}};
	queue<string> q{{beginWord}};
	
	while (!q.empty()) 
	{
		string word = q.front(); q.pop();
		for (int i = 0; i < word.size(); ++i) 
		{
			string newWord = word;
			for (char ch = 'a'; ch <= 'z'; ++ch) 
			{
				newWord[i] = ch;
				if (wordSet.count(newWord) && newWord == endWord) 
					return pathCnt[word] + 1;
				if (wordSet.count(newWord) && !pathCnt.count(newWord)) 
				{
					q.push(newWord);
					pathCnt[newWord] = pathCnt[word] + 1;
				}   
			}
		}
	}
	return 0;
}

int ladderLength_two_end_bfs(string beginWord, string endWord, vector<string>& wordList) 
{
	unordered_set<string> dict(wordList.begin(), wordList.end());
	if (dict.count(endWord) == 0) return 0;

	unordered_set<string> string1 = {beginWord};
	unordered_set<string> string2 = {endWord};
	dict.erase(endWord);
	int step = 0;

	while (!string1.empty() && !string2.empty()) 
	{
	    step++;
	    if (string1.size() > string2.size()) swap(string1, string2);
	    unordered_set<string> temp;

	    for (auto word : string1) 
	    {
	        for (int i=0; i<word.size(); i++) 
	        {
	            char oldChar = word[i];
	            for (char c='a'; c<='z'; c++) 
	            {
	                if (c == oldChar) continue;
	                string newWord = word;
	                newWord[i] = c;
	                if (string2.count(newWord)) 
	                	return step+1;

	                if (dict.count(newWord)) 
	                {
	                    temp.insert(newWord);
	                    dict.erase(newWord);
	                }
	            }
	        }
	    }
	    swap(string1, temp);
	}
	return 0;
}


int main() 
{ 
    vector<string> wordList; 
    wordList.push_back("hot");
    wordList.push_back("dot");
    wordList.push_back("dog");
    wordList.push_back("lot");
    wordList.push_back("log");
    wordList.push_back("cog");
    string beginWord  = "hit"; 
    string endWord  = "cog"; 

    cout << "Length of shortest chain using 上 e end BFS is: "<< ladderLength_bfs(beginWord, endWord, wordList)<<endl;  
   	cout << "Length of shortest chain using two end BFS is: "<< ladderLength_two_end_bfs(beginWord, endWord, wordList)<<endl;  

    return 0;  
}

输出：

Length of shortest chain using 上 e end BFS is: 5
Length of shortest chain using two end BFS is: 5

该网站上可用的教程列表：