Word Ladder II
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
这道题是leetcode上通过率最低的一道题,Max Points on a Line是因为出的比较晚,但是并不难,这道题,好嘛,DFS超时,BFS超时,提交了十次都木有过,太尼玛丧心病狂了!
careercup上也有这道题,但是只需要找出一条最短路径即可,相对来说简单的多,这道题实在吐槽无力,从网上找到了一个大神写的,相对而言逻辑最清晰的一篇。由于源代码是在论坛回帖中,作者无从考证。大家还是直接看代码吧。
这里有两点可以留意一下:(本解法用的邻接表法)
1. 构建graph的时候的时候用的String,回溯的时候用的node节点
2. 切断了“父节点”之间和兄弟之间的相邻关系,从而使得parent节点只有一个
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) { // Start typing your Java solution below // DO NOT write main() function HashMap<String, HashSet<String>> neighbours = new HashMap<String, HashSet<String>>(); dict.add(start); dict.add(end); // init adjacent graph for(String str : dict){ calcNeighbours(neighbours, str, dict); } ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); // BFS search queue LinkedList<Node> queue = new LinkedList<Node>(); queue.add(new Node(null, start, 1)); // BFS level int previousLevel = 0; // mark which nodes have been visited, to break infinite loop HashMap<String, Integer> visited = new HashMap<String, Integer>(); while(!queue.isEmpty()){ Node n = queue.pollFirst(); if(end.equals(n.str)){ // fine one path, check its length, if longer than previous path it's valid // otherwise all possible short path have been found, should stop if(previousLevel == 0 || n.level == previousLevel){ previousLevel = n.level; findPath(n, result); }else { // all path with length *previousLevel* have been found break; } }else { HashSet<String> set = neighbours.get(n.str); if(set == null || set.isEmpty()) continue; // note: I'm not using simple for(String s: set) here. This is to avoid hashset's // current modification exception. ArrayList<String> toRemove = new ArrayList<String>(); for (String s : set) { // if s has been visited before at a smaller level, there is already a shorter // path from start to s thus we should ignore s so as to break infinite loop; if // on the same level, we still need to put it into queue. if(visited.containsKey(s)){ Integer occurLevel = visited.get(s); if(n.level+1 > occurLevel){ neighbours.get(s).remove(n.str); toRemove.add(s); continue; } } visited.put(s, n.level+1); queue.add(new Node(n, s, n.level + 1)); if(neighbours.containsKey(s)) neighbours.get(s).remove(n.str); } for(String s: toRemove){ set.remove(s); } } } return result; } public void findPath(Node n, ArrayList<ArrayList<String>> result){ ArrayList<String> path = new ArrayList<String>(); Node p = n; while(p != null){ path.add(0, p.str); p = p.parent; } result.add(path); } /* * complexity: O(26*str.length*dict.size)=O(L*N) */ void calcNeighbours(HashMap<String, HashSet<String>> neighbours, String str, HashSet<String> dict) { int length = str.length(); char [] chars = str.toCharArray(); for (int i = 0; i < length; i++) { char old = chars[i]; for (char c = 'a'; c <= 'z'; c++) { if (c == old) continue; chars[i] = c; String newstr = new String(chars); if (dict.contains(newstr)) { HashSet<String> set = neighbours.get(str); if (set != null) { set.add(newstr); } else { HashSet<String> newset = new HashSet<String>(); newset.add(newstr); neighbours.put(str, newset); } } } chars[i] = old; } } private class Node { public Node parent; public String str; public int level; public Node(Node p, String s, int l){ parent = p; str = s; level = l; } }
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
word_ladder问题源代码 算法导论
Linux环境下写的。用了Stanford的库,wordladder以及randomwritter,仅供新手参考,有问题大家一起交流
LADDERii_MANUAL,FANUC 工具機的控制器PMC編程說明手冊,可提供編程者規劃程序時使用。
BluePrism.WordLadder 这是用C#编写的用于解决Word Ladder的命令行。 第一个版本使用图算法。#BluePrism.WordLadder
Ladder with authenticating user 1. 实现spring security的四种方法 1. 全部利用配置文件 不使用数据库,全部信息写在配置文件中,如拦截的URL及对应权限,指定用户名、密码和对应权限 2. 数据库+配置文件 数据库...
wordLadder_web 查看位于的页面
6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 ...
SOFTWARE FAPT LADDER.
FANUC LADDER III软件中文教程pdf,FANUC LADDER III软件中文教程
GUTTA Ladder Editor 1.1 PLC可编程逻辑控制器编程工具
FANUC LADDER-III V8.7 PMC编程软件
FANUC LADDER PMC 辅助工具.zip
FANUC LADDER-III V8.9最新升级包
fapt ladder III 2.1.rar
fanuc ladder 7.5是一款专门用来编写FANUC PMC程序的数控编程软件,主要是为了诊断和维护数控PMC顺序程序,Fanuc PLC集成。fanuc ladder iii可以通过内嵌以太网与电脑相连,线上上传、下载PMC相关文件,让用户可以...
FANUC LADDER-III V8.0最新版 FANUC梯形图软件最新版
PLC仿真工具GUTTA Ladder Editor,中文工具,简单易用,功能强大
FANUC LADDER-III V7.5附带序列号汉化包,点击文件夹内的 FL3AutoRun.exe 即可打开安装程序,安装过程中“Serial”表示需要输入序列号,安装完后进入汉化包文件夹,阅读 Readme.txt按照说明即可免费将软件汉化