#include <iostream>#include <stdio.h>#include <vector>#include <unordered_map>#include <string>#include <map>#include <queue>using namespace std;/*問題:Given two Words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:Only one letter can be changed at a timeEach 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"]Return  [    ["hit","hot","dot","dog","cog"],    ["hit","hot","lot","log","cog"]  ]Note:Return an empty list 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.UPDATE (2017/1/20):The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.分析:這是程序員面試金典的一道題目。給定兩個字符串和一個單詞列表，每次只能變換一個字符，求從初始字符串變換到結束字符串變換次數最少的序列，如果序列有多個，請全部返回。如果不存在這樣的變換序列，返回空列表。采用暴力破解：對初始字符串的每個字符進行從'a'到'z'的變換，如果變換后的字符串在變換列表中繼續嘗試變換下一個字符。否則說明當前變換的字符不符合，就先變換下一個字符這個應該是回溯，一旦當前字符擺放不成功，要回溯到原來的狀態遞歸，并保存一個當前最短序列的值，如果當前擺放轉換次數已經大于最少序列的值，直接放棄這一轉換，回退到頂點繼續輸入:hit(起始單詞) cog(結束單詞) 6(單詞數組元素個數)hot dot dog lot log coghit cog 5hot dot dog lot loghot dog 3hot dog dot輸出:hit hot dot dog cog, hit hot lot log cogno resulthot dot dog超時:回溯主要是對每個字符都嘗試進行變換來獲取下一個回溯的字符串，這個很慢程序員面試金典的做法：建一個map<string, vector<string> >，其中鍵是某個單詞，值是這個單詞只變換一個字符的所有可能下的下一個字符串列表采用隊列+獲取當前單詞，對當前單詞所有可能的只需要一次字符變換的數組繼續遍歷還是超時了。應該是我提前把所有的變位詞計算出來后，耗時過長，如果每次遇到新的變位詞，才去計算，并將計算結果保存，不就行了嗎?還是超時關鍵:1 參考這位的解法:https://leetcode.com/PRoblems/word-ladder-ii/?tab=Solutions另外一種解法是找到一條最短的距離（通過bfs）minDis，并且在遍歷過程中存儲任意字符串到初始字符串的距離。那么dfs搜索的時候采用當前結點的下一個結點遍歷的時候需要滿足下一個結點距離初始結點的距離=當前結點距離初始結點的距離+1否則，就剪枝，不遞歸。*/class Solution {public:	//獲取某個單詞的所有變位詞	vector<string> getOneEditWords(string& beginWord , vector<string>& wordList, unordered_map<string ,int>& words,unordered_map<string , vector<string> >& wordToNextWords)	{		//如果已經計算過了，就直接返回		if(1 == wordToNextWords.count(beginWord))		{			return  wordToNextWords[beginWord];		}		//求出開始單詞的可經過一次變換的所有字符串		vector<string> begNextWords;		char temp;		int len;		if(!beginWord.empty())		{			len = beginWord.length();			for(int i = 0; i < len ; i++)			{				temp = beginWord.at(i);				for(char ch = 'a' ;  ch <= 'z' ; ch++)				{					if(temp == ch)					{						continue;					}					beginWord.at(i) = ch;					//如果新的單詞，在單詞列表中存在，就加入結果集					if(1 == words.count(beginWord))					{						begNextWords.push_back(beginWord);					}					beginWord.at(i) = temp;				}			}			wordToNextWords[beginWord] = begNextWords;		}		return begNextWords;	}	//獲取所有字符串距離初始字符串的距離映射，以及最少變換次數	int bfs(string& beginWord, string& endWord, vector<string>& wordList,		unordered_map<string , vector<string>>& wordToNextWords , 		unordered_map<string,int>& words, unordered_map<string,int>& strToDistance)	{		queue<string> queueWords;		queueWords.push(beginWord);		strToDistance[beginWord] = 0;//初始字符串到自身距離為0		string word;		string nextWord;		vector<string> nextWords;		int curDis = 0;		int size;		unordered_map<string ,int> visited;		bool isFound = false;		while(!queueWords.empty())		{			word = queueWords.front();			queueWords.pop();			nextWords = getOneEditWords(word , wordList, words , wordToNextWords);			if(nextWords.empty())			{				continue;			}			//當前距離是從映射中獲取的			curDis = -1;			if(strToDistance.find(word) != strToDistance.end())			{				curDis = strToDistance[word];			}			size = nextWords.size();			for(int i = 0 ; i < size ; i++)			{				nextWord = nextWords.at(i);				//當前結點必須是未訪問過的，不行有些結點需要用到之前訪問過的				//設置當前結點距離初始結點的距離				if(strToDistance.find(nextWord) == strToDistance.end())				{					strToDistance[ nextWord] = curDis + 1;					//判斷當前字符串是否等于結束字符串，就直接退出					if(nextWord == endWord)					{						isFound = true;						//break;//不能直接退出，當前層的其他元素需要設置該距離					}					//將當前字符串壓入到隊列中					queueWords.push(nextWord);				}			}			if(isFound)			{				break;			}		}		if(isFound)		{			return curDis;//這個距離是倒數第二個結點距離初始結點的距離，實際距離=curDis+1		}		else		{			return -1;		}	}	void dfs(string& beginWord, string& endWord,unordered_map<string,int>& words, vector<string> result,		vector< vector<string> >& results,unordered_map<string , vector<string>>& wordToNextWords , 		vector<string>& wordList, unordered_map<string,int>& strToDistance)	{		result.push_back(beginWord);		//找到了，返回		if(beginWord == endWord)		{			results.push_back(result);			return;		}		vector<string> nextWords = getOneEditWords(beginWord , wordList  , words , wordToNextWords);		if(nextWords.empty())		{			return ;		}		int size = nextWords.size();		string nextWord;		for(int i = 0 ; i < size ; i++)		{			nextWord = nextWords.at(i);			//牛逼，剪枝，將下一個結點集合中所有與當前結點到初始結點距離+1 不等的全部過濾			if(strToDistance[nextWord] == strToDistance[beginWord] + 1)			{				dfs(nextWord, endWord, words , result , results, wordToNextWords, wordList , strToDistance);			}		}	}    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        vector<vector<string>> results;		if(beginWord.empty() || endWord.empty() || wordList.empty())		{			return results;		}		vector<string> result;		int size = wordList.size();		unordered_map<string ,int> words;		for(int i =  0; i < size ; i++)		{			words[ wordList.at(i) ] = 1;		}		int minSequence = INT_MAX;		unordered_map<string ,int> visited;		unordered_map<string , vector<string>> wordToNextWords; //= getOneEditMap(beginWord , wordList , words);		unordered_map<string , int> strToDistance;		bfs(beginWord , endWord, wordList , wordToNextWords, words ,strToDistance);		dfs(beginWord, endWord, words, result , results , wordToNextWords , wordList , strToDistance);		return results;    }};void print(vector<vector<string> >& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	int len;	for(int i = 0 ; i < size ; i++)	{		len = result.at(i).size();		for(int j = 0 ; j < len ; j++)		{			cout << result.at(i).at(j) << " " ;		}		cout << ",";	}	cout << endl;}void process(){	 vector<string> nums;	 string value;	 int num;	 Solution solution;	 string beginWord;	 string endWord;	 vector<vector<string> > result;	 while(cin >> beginWord >> endWord >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 result = solution.findLadders(beginWord , endWord , nums);		 print(result);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*	void dfs2(string& beginWord, string& endWord,unordered_map<string,int>& words, vector<string>& result, 		vector< vector<string> >& results, int& minSequenceLen, unordered_map<string ,int>& visited,		unordered_map<string , vector<string>>& wordToNextWords , vector<string>& wordList)	{		//結果集中字符串個數 >= 最小序列長度,肯定不可能，返回false		if(!result.empty() && result.size() > minSequenceLen )		{			return;		}		//找到一份結果		if(!result.empty() && result.at( result.size() - 1 ) == endWord)		{			//更新最短序列的值,當前記錄的結果長度比原先還要短，則原先的全部清除			if(result.size() < minSequenceLen)			{				results.clear();				minSequenceLen = result.size();			}			results.push_back(result);			return;		}		//接下來獲取每個字符串的下一個字符串		//unordered_map<string, vector<string> >::iterator it = wordToNextWords.find(beginWord);		//如果找不到，就計算		vector<string> nextWords = getOneEditWords(beginWord , wordList  , words , wordToNextWords);		if(nextWords.empty())		{			return ;		}		int size = nextWords.size();		string nextWord;		for(int i = 0 ; i < size ; i++)		{			nextWord = nextWords.at(i);			//如果找到當前變換的字符，就繼續遞歸向下尋找，并把當前字符串插入到其中,必須區分已經存在的字符串			//if(1 == words.count(nextWord) && 0 == visited.count(nextWord))//字典中存在,并且是未被訪問過的			if(0 == visited.count(nextWord))//字典中存在,并且是未被訪問過的			{				result.push_back(nextWord);				//設置訪問標記				visited[nextWord] = 1;				dfs2(nextWord , endWord, words , result, results, minSequenceLen ,visited , wordToNextWords , wordList);				//回溯				result.pop_back();				visited.erase(nextWord);			}		}	}	//獲取每個單詞經過一個字符變換對應的字符串列表,估計是計算這個表耗時了	unordered_map<string , vector<string>> getOneEditMap(string beginWord , vector<string>& wordList, unordered_map<string ,int>& words)	{		unordered_map<string , vector<string> > wordToNextWords;		//求出開始單詞的可經過一次變換的所有字符串		vector<string> begNextWords;		char temp;		int len;		if(!beginWord.empty())		{			len = beginWord.length();			for(int i = 0; i < len ; i++)			{				temp = beginWord.at(i);				for(char ch = 'a' ;  ch <= 'z' ; ch++)				{					if(temp == ch)					{						continue;					}					beginWord.at(i) = ch;					//如果新的單詞，在單詞列表中存在，就加入結果集					if(1 == words.count(beginWord))					{						begNextWords.push_back(beginWord);					}					beginWord.at(i) = temp;				}			}			wordToNextWords[beginWord] = begNextWords;		}		int size = wordList.size();		for(int j = 0 ; j < size ; j++ )		{			vector<string> nextWords;			beginWord = wordList.at(j);			len = beginWord.length();			for(int i = 0; i < len ; i++)			{				temp = beginWord.at(i);				for(char ch = 'a' ;  ch <= 'z' ; ch++)				{					if(temp == ch)					{						continue;					}					beginWord.at(i) = ch;					//如果新的單詞，在單詞列表中存在，就加入結果集					if(1 == words.count(beginWord))					{						nextWords.push_back(beginWord);					}					beginWord.at(i) = temp;				}			}			wordToNextWords[beginWord] = nextWords;		}		return wordToNextWords;	}	//用廣度優先搜索來做	void bfs(string& beginWord, string& endWord,unordered_map<string,int>& words,		unordered_map<string , vector<string>>& wordToNextWords)	{		vector<string> result;		vector< vector<string> > results;		int minSequenceLen = INT_MAX;		unordered_map<string ,int> visited;		queue<string> queueWords;		queueWords.push(beginWord);		string word;		vector<string> nextWords;		string nextWord;		int size;		while(!queueWords.empty())		{			word = queueWords.front();			queueWords.pop();			//尋找下一個單詞			if(0 == wordToNextWords.count(word))			{				continue;			}			nextWords = wordToNextWords[word];			if(nextWords.empty())			{				continue;			}			size = nextWords.size();			for(int i = 0 ; i < size ; i++)			{				nextWord = nextWords.at(i);				//如果當前單詞已經訪問過了				if(1 == visited.count(nextWord))				{					continue;				}				//沒有訪問過，將當前單詞壓入隊列			}		}	}超時正確版本class Solution {public:	void dfs(string beginWord, string& endWord,unordered_map<string,int> words, vector<string>& result, 		vector< vector<string> >& results, int& minSequenceLen, unordered_map<string ,int>& visited)	{		//結果集中字符串個數 >= 最小序列長度,肯定不可能，返回false		if(!result.empty() && result.size() > minSequenceLen )		{			return;		}		//找到一份結果		if(!result.empty() && result.at( result.size() - 1 ) == endWord)		{			//更新最短序列的值,當前記錄的結果長度比原先還要短，則原先的全部清除			if(result.size() < minSequenceLen)			{				results.clear();				minSequenceLen = result.size();			}			results.push_back(result);			return;		}		//接下來嘗試變換字符		int len = beginWord.length();		char temp;		for(int i = 0 ; i < len ; i++)		{			//對位置i上進行嘗試，			temp = beginWord.at(i);			for(char ch = 'a' ; ch <= 'z' ; ch++)			{				//跳過當前字符本身				if(temp == ch)				{					continue;				}				beginWord.at(i) = ch;				//如果找到當前變換的字符，就繼續遞歸向下尋找，并把當前字符串插入到其中,必須區分已經存在的字符串				if(1 == words.count(beginWord) && 0 == visited.count(beginWord))//字典中存在,并且是未被訪問過的				{					result.push_back(beginWord);					//設置訪問標記					visited[beginWord] = 1;					dfs(beginWord , endWord, words , result, results, minSequenceLen ,visited);					//回溯					result.pop_back();					visited.erase(beginWord);				}				//回溯，重新設定為原來狀態				beginWord.at(i) = temp;			}		}	}    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {        vector<vector<string>> results;		if(beginWord.empty() || endWord.empty() || wordList.empty())		{			return results;		}		vector<string> result;		result.push_back(beginWord);		int size = wordList.size();		unordered_map<string ,int> words;		for(int i =  0; i < size ; i++)		{			words[ wordList.at(i) ] = 1;		}		int minSequence = INT_MAX;		unordered_map<string ,int> visited;		dfs(beginWord, endWord, words, result , results , minSequence , visited);		return results;    }};*/