回溯题目：单词接龙 II

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题单词接龙 II出处126. 单词接龙 II难度8 级题目描述要求字典wordList \texttt{wordList}wordList中从开始单词beginWord \texttt{beginWord}beginWord到结束单词endWord \texttt{endWord}endWord的转换序列是一个按下述规格形成的序列beginWord → s 1 → s 2 → … → s k \texttt{beginWord} \rightarrow \texttt{s}_\texttt{1} \rightarrow \texttt{s}_\texttt{2} \rightarrow \ldots \rightarrow \texttt{s}_\texttt{k}beginWord→s1​→s2​→…→sk​每一对相邻的单词只差一个字母。对于1 ≤ i ≤ k \texttt{1} \le \texttt{i} \le \texttt{k}1≤i≤k每个s i \texttt{s}_\texttt{i}si​都在wordList \texttt{wordList}wordList中。注意beginWord \texttt{beginWord}beginWord不需要在wordList \texttt{wordList}wordList中。s k endWord \texttt{s}_\texttt{k} \texttt{endWord}sk​endWord给定两个单词beginWord \texttt{beginWord}beginWord和endWord \texttt{endWord}endWord以及一个字典wordList \texttt{wordList}wordList返回所有从beginWord \texttt{beginWord}beginWord到endWord \texttt{endWord}endWord的最短转换序列。如果不存在这样的转换序列返回空列表。每个序列都应该以单词列表[beginWord, s 1 , s 2 , … , s k ] \texttt{[beginWord, s}_\texttt{1}\texttt{, s}_\texttt{2}\texttt{, }\ldots\texttt{, s}_\texttt{k}\texttt{]}[beginWord, s1​, s2​,…, sk​]的形式返回。示例示例 1输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog] \texttt{beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog]}beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log,cog]输出[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]] \texttt{[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]]}[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]]解释存在2 \texttt{2}2种最短的转换序列hit → hot → dot → dog → cog \texttt{hit} \rightarrow \texttt{hot} \rightarrow \texttt{dot} \rightarrow \texttt{dog} \rightarrow \texttt{cog}hit→hot→dot→dog→coghit → hot → lot → log → cog \texttt{hit} \rightarrow \texttt{hot} \rightarrow \texttt{lot} \rightarrow \texttt{log} \rightarrow \texttt{cog}hit→hot→lot→log→cog示例 2输入beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log] \texttt{beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log]}beginWord hit, endWord cog, wordList [hot,dot,dog,lot,log]输出[] \texttt{[]}[]解释结束单词cog \texttt{cog}cog不在字典中所以不存在有效的转换序列。数据范围1 ≤ beginWord.length ≤ 5 \texttt{1} \le \texttt{beginWord.length} \le \texttt{5}1≤beginWord.length≤5endWord.length beginWord.length \texttt{endWord.length} \texttt{beginWord.length}endWord.lengthbeginWord.length1 ≤ wordList.length ≤ 500 \texttt{1} \le \texttt{wordList.length} \le \texttt{500}1≤wordList.length≤500wordList[i].length beginWord.length \texttt{wordList[i].length} \texttt{beginWord.length}wordList[i].lengthbeginWord.lengthbeginWord \texttt{beginWord}beginWord、endWord \texttt{endWord}endWord和wordList[i] \texttt{wordList[i]}wordList[i]由小写英语字母组成beginWord ≠ endWord \texttt{beginWord} \ne \texttt{endWord}beginWordendWordwordList \texttt{wordList}wordList中的所有字符串各不相同所有最短转换序列的长度之和不超过10 5 \texttt{10}^\texttt{5}105解法思路和算法这道题是「单词接龙」的进阶要求计算所有从beginWord \textit{beginWord}beginWord到endWord \textit{endWord}endWord的最短转换序列。需要首先判断转换序列是否存在当转换序列存在时再生成所有的最短转换序列。为了快速判断一个单词是否在字典中需要使用哈希集合存储字典中的每个单词。只有当endWord \textit{endWord}endWord在字典中时才可能存在从beginWord \textit{beginWord}beginWord到endWord \textit{endWord}endWord的转换序列因此首先判断endWord \textit{endWord}endWord是否在字典中如果endWord \textit{endWord}endWord不在字典中则不存在从beginWord \textit{beginWord}beginWord到endWord \textit{endWord}endWord的转换序列返回空列表。以下只考虑endWord \textit{endWord}endWord在字典中的情况。判断转换序列是否存在可以使用广度优先搜索实现当转换序列存在时广度优先搜索可以确保得到最短转换序列。广度优先搜索的过程中需要使用哈希集合存储已访问的单词。初始时将beginWord \textit{beginWord}beginWord添加到已访问的哈希集合将beginWord \textit{beginWord}beginWord入队列。为了生成所有的最短转换序列广度优先搜索的过程中需要记录最短转换序列中的相邻单词之间的关系。具体做法是使用两个哈希表分别记录每个单词所在的层数和每个单词的前驱单词集合两个哈希表分别为层数哈希表和前驱哈希表。规定beginWord \textit{beginWord}beginWord在第1 11层从beginWord \textit{beginWord}beginWord开始遍历每次遍历同一层的全部单词并得到下一层的全部单词。记当前层为level \textit{level}level对于当前层的每个单词word \textit{word}word执行如下操作。如果word endWord \textit{word} \textit{endWord}wordendWord则找到转换序列结束广度优先搜索。如果word ≠ endWord \textit{word} \ne \textit{endWord}wordendWord则执行后续操作。得到word \textit{word}word的所有相邻单词对于每个相邻单词adjacent \textit{adjacent}adjacent执行如下操作。如果adjacent \textit{adjacent}adjacent在层数哈希表中存在且对应层数为level 1 \textit{level} 1level1则adjacent \textit{adjacent}adjacent为word \textit{word}word的后继单词word \textit{word}word为adjacent \textit{adjacent}adjacent的前驱单词将word \textit{word}word添加到adjacent \textit{adjacent}adjacent的前驱单词集合中。否则如果adjacent \textit{adjacent}adjacent在字典中且尚未加入已访问的哈希集合则将adjacent \textit{adjacent}adjacent加入已访问的哈希集合将adjacent \textit{adjacent}adjacent和对应层数level 1 \textit{level} 1level1添加到层数哈希表将word \textit{word}word添加到adjacent \textit{adjacent}adjacent的前驱单词集合中将adjacent \textit{adjacent}adjacent入队列。如果遍历结束仍未发现endWord \textit{endWord}endWord则不存在转换序列。当存在转换序列时从endWord \textit{endWord}endWord开始回溯得到所有的最短转换序列。用word \textit{word}word表示当前单词从前驱哈希表得到word \textit{word}word的所有前驱单词对于每个前驱单词执行回溯每次遇到beginWord \textit{beginWord}beginWord时即得到一个从endWord \textit{endWord}endWord到beginWord \textit{beginWord}beginWord的最短转换序列将该序列反转之后得到一个从beginWord \textit{beginWord}beginWord到endWord \textit{endWord}endWord的最短转换序列。代码classSolution{ListListStringladdersnewArrayListListString();StringbeginWord;intwordLength;MapString,SetStringprevMapnewHashMapString,SetString();ListStringtempnewArrayListString();publicListListStringfindLadders(StringbeginWord,StringendWord,ListStringwordList){SetStringwordSetnewHashSetString();for(Stringword:wordList){wordSet.add(word);}if(!wordSet.contains(endWord)){returnladders;}this.beginWordbeginWord;this.wordLengthbeginWord.length();booleanfoundbfs(beginWord,endWord,wordSet);if(found){backtrack(endWord);}returnladders;}publicbooleanbfs(StringbeginWord,StringendWord,SetStringwordSet){SetStringvisitednewHashSetString();visited.add(beginWord);MapString,IntegerlevelMapnewHashMapString,Integer();levelMap.put(beginWord,1);QueueStringqueuenewArrayDequeString();queue.offer(beginWord);intlevel0;while(!queue.isEmpty()){level;intsizequeue.size();for(inti0;isize;i){Stringwordqueue.poll();if(word.equals(endWord)){returntrue;}ListStringadjacentWordsgetAdjacentWords(word);for(Stringadjacent:adjacentWords){if(levelMap.getOrDefault(adjacent,0)level1){prevMap.get(adjacent).add(word);}elseif(wordSet.contains(adjacent)visited.add(adjacent)){levelMap.put(adjacent,level1);prevMap.put(adjacent,newHashSetString());prevMap.get(adjacent).add(word);queue.offer(adjacent);}}}}returnfalse;}publicListStringgetAdjacentWords(Stringword){ListStringadjacentWordsnewArrayListString();char[]arrword.toCharArray();for(inti0;iwordLength;i){charoriginalarr[i];for(charca;cz;c){if(coriginal){continue;}arr[i]c;adjacentWords.add(newString(arr));}arr[i]original;}returnadjacentWords;}publicvoidbacktrack(Stringword){temp.add(word);if(word.equals(beginWord)){ListStringladdernewArrayListString(temp);Collections.reverse(ladder);ladders.add(ladder);}else{SetStringprevWordsprevMap.get(word);for(Stringprev:prevWords){backtrack(prev);}}temp.remove(temp.size()-1);}}复杂度分析时间复杂度O ( ∣ Σ ∣ × m × n m × L ) O(|\Sigma| \times m \times n m \times L)O(∣Σ∣×m×nm×L)其中Σ \SigmaΣ是字符集m mm是单词的长度n nn是字典的大小L LL是所有最短转换序列的长度之和这道题中Σ \SigmaΣ是全部小写英语字母∣ Σ ∣ 26 |\Sigma| 26∣Σ∣26。广度优先搜索最多需要遍历每个单词一次对于每个单词计算其下一层的单词的时间是O ( ∣ Σ ∣ × m ) O(|\Sigma| \times m)O(∣Σ∣×m)因此时间复杂度是O ( ∣ Σ ∣ × m × n ) O(|\Sigma| \times m \times n)O(∣Σ∣×m×n)。回溯时对于最短转换序列中的每个单词的操作时间是O ( m ) O(m)O(m)因此时间复杂度是O ( m × L ) O(m \times L)O(m×L)。总时间复杂度是O ( ∣ Σ ∣ × m × n m × L ) O(|\Sigma| \times m \times n m \times L)O(∣Σ∣×m×nm×L)。空间复杂度O ( m × n ) O(m \times n)O(m×n)其中m mm是单词的长度n nn是字典的大小。哈希集合、哈希表和队列需要O ( m × n ) O(m \times n)O(m×n)的空间。注意返回值不计入空间复杂度。