leetcode-127-单词接龙-java

题目及测试

package pid127;
/* 单词接龙给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：每次转换只能改变一个字母。转换过程中的中间单词必须是字典中的单词。说明:如果不存在这样的转换序列，返回 0。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。你可以假设 beginWord 和 endWord 是非空的，且二者不相同。示例 1:输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]输出: 5解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",返回它的长度 5。示例 2:输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]输出: 0解释: endWord "cog" 不在字典中，所以无法进行转换。*/import java.util.ArrayList;
import java.util.List;public class main {public static void main(String[] args) {String ito1="hit";String ito2="cog";List list=new ArrayList();list.add("hot");list.add("dot");list.add("dog");list.add("lot");list.add("log");list.add("cog");test(ito1, ito2, list);}private static void test(String ito1,String ito2,List list) {Solution solution = new Solution();int rtn;long begin = System.currentTimeMillis();System.out.print(ito1+" "+ito2+" "+list);		    System.out.println();//开始时打印数组rtn= solution.ladderLength(ito1,ito2,list);//执行程序long end = System.currentTimeMillis();	System.out.println("rtn=" );System.out.print(rtn);System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}

解法1（超时）

拥有一个 beginWord 和一个 endWord，分别表示图上的 start node 和 end node。我们希望利用一些中间节点（单词）从 start node 到 end node，中间节点是 wordList 给定的单词。我们对这个单词接龙每个步骤的唯一条件是相邻单词只可以改变一个字母。

我们将问题抽象在一个无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。

算法中最重要的步骤是找出相邻的节点，也就是只差一个字母的两个单词。为了快速的找到这些相邻节点，我们对给定的 wordList 做一个预处理，将单词中的某个字母用 * 代替。

这个预处理帮我们构造了一个单词变换的通用状态。例如：Dog ----> D*g <---- Dig，Dog 和 Dig 都指向了一个通用状态 D*g。

这步预处理找出了单词表中所有单词改变某个字母后的通用状态，并帮助我们更方便也更快的找到相邻节点。否则，对于每个单词我们需要遍历整个字母表查看是否存在一个单词与它相差一个字母，这将花费很多时间。预处理操作在广度优先搜索之前高效的建立了邻接表。

例如，在广搜时我们需要访问 Dug 的所有邻接点，我们可以先生成 Dug 的所有通用状态：

    Dug => *ug
    Dug => D*g
    Dug => Du*

第二个变换 D*g 可以同时映射到 Dog 或者 Dig，因为他们都有相同的通用状态。拥有相同的通用状态意味着两个单词只相差一个字母，他们的节点是相连的。

利用广度优先搜索搜索从 beginWord 到 endWord 的路径。

对给定的 wordList 做预处理，找出所有的通用状态。将通用状态记录在字典中，键是通用状态，值是所有具有通用状态的单词。

将包含 beginWord 和 1 的元组放入队列中，1 代表节点的层次。我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。

为了防止出现环，使用访问数组记录。

当队列中有元素的时候，取出第一个元素，记为 current_word。

找到 current_word 的所有通用状态，并检查这些通用状态是否存在其它单词的映射，这一步通过检查 all_combo_dict 来实现。

从 all_combo_dict 获得的所有单词，都和 current_word 共有一个通用状态，所以都和 current_word 相连，因此将他们加入到队列中。

对于新获得的所有单词，向队列中加入元素 (word, level + 1) 其中 level 是 current_word 的层次。

最终当你到达期望的单词，对应的层次就是最短变换序列的长度。

public class Solution {HashMap> mapPositive = new HashMap>();HashMap> mapNegative = new HashMap>();HashMap mapVisit = new HashMap();int result = Integer.MAX_VALUE;public int ladderLength(String beginWord, String endWord, List wordList) {for(int i=0;i list;if(mapPositive.containsKey(word)) {list = mapPositive.get(word);}else {list = new ArrayList();mapPositive.put(word, list);}list.add(regex);if(mapNegative.containsKey(regex)) {list = mapNegative.get(regex);}else {list = new ArrayList();mapNegative.put(regex, list);}list.add(word);chars[i] = now;}mapVisit.put(word, false);}private void findEnd(String nowWord,String endWord,int nowStep) {if(endWord.equals(nowWord)) {if(nowStep < result) {result = nowStep;}return;}List candidates = getCandidates(nowWord);if(candidates == null || candidates.size() == 0) {return;}for(int i=0;i getCandidates(String word){List list = mapPositive.get(word);if(list == null) {return new ArrayList();}Set set = new HashSet();for(int i=0;i regexList = mapNegative.get(regex);if(regexList == null) {continue;}for(int j=0;j candidates = new ArrayList();for(String string:set) {candidates.add(string);}return candidates;}}

解法2（别人的）

根据给定字典构造的图可能会很大，而广度优先搜索的搜索空间大小依赖于每层节点的分支数量。假如每个节点的分支数量相同，搜索空间会随着层数的增长指数级的增加。考虑一个简单的二叉树，每一层都是满二叉树的扩展，节点的数量会以 2 为底数呈指数增长。

如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一个节点，当发现某一时刻两边都访问了某一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而降低时间和空间复杂度。

算法与之前描述的标准广搜方法相类似。

唯一的不同是我们从两个节点同时开始搜索，同时搜索的结束条件也有所变化。

我们现在有两个访问数组，分别记录从对应的起点是否已经访问了该节点。

如果我们发现一个节点被两个搜索同时访问，就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。

双向搜索的结束条件是找到一个单词被两边搜索都访问过了。

最短变换序列的长度就是中间节点在两边的层次之和。因此，我们可以在访问数组中记录节点的层次。

import javafx.util.Pair;class Solution {private int L;private HashMap> allComboDict;Solution() {this.L = 0;// Dictionary to hold combination of words that can be formed,// from any given word. By changing one letter at a time.this.allComboDict = new HashMap>();}private int visitWordNode(Queue> Q,HashMap visited,HashMap othersVisited) {Pair node = Q.remove();String word = node.getKey();int level = node.getValue();for (int i = 0; i < this.L; i++) {// Intermediate words for current wordString newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);// Next states are all the words which share the same intermediate state.for (String adjacentWord : this.allComboDict.getOrDefault(newWord, new ArrayList())) {// If at any point if we find what we are looking for// i.e. the end word - we can return with the answer.if (othersVisited.containsKey(adjacentWord)) {return level + othersVisited.get(adjacentWord);}if (!visited.containsKey(adjacentWord)) {// Save the level as the value of the dictionary, to save number of hops.visited.put(adjacentWord, level + 1);Q.add(new Pair(adjacentWord, level + 1));}}}return -1;}public int ladderLength(String beginWord, String endWord, List wordList) {if (!wordList.contains(endWord)) {return 0;}// Since all words are of same length.this.L = beginWord.length();wordList.forEach(word -> {for (int i = 0; i < L; i++) {// Key is the generic word// Value is a list of words which have the same intermediate generic word.String newWord = word.substring(0, i) + '*' + word.substring(i + 1, L);ArrayList transformations =this.allComboDict.getOrDefault(newWord, new ArrayList());transformations.add(word);this.allComboDict.put(newWord, transformations);}});// Queues for birdirectional BFS// BFS starting from beginWordQueue> Q_begin = new LinkedList>();// BFS starting from endWordQueue> Q_end = new LinkedList>();Q_begin.add(new Pair(beginWord, 1));Q_end.add(new Pair(endWord, 1));// Visited to make sure we don't repeat processing same word.HashMap visitedBegin = new HashMap();HashMap visitedEnd = new HashMap();visitedBegin.put(beginWord, 1);visitedEnd.put(endWord, 1);while (!Q_begin.isEmpty() && !Q_end.isEmpty()) {// One hop from begin wordint ans = visitWordNode(Q_begin, visitedBegin, visitedEnd);if (ans > -1) {return ans;}// One hop from end wordans = visitWordNode(Q_end, visitedEnd, visitedBegin);if (ans > -1) {return ans;}}return 0;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！