原题链接:http://oj.leetcode.com/problems/word-ladder-ii/
这道题是LeetCode中AC率最低的题目,确实是比较难。一方面是因为对时间有比较严格的要求(容易超时),另一方面是它有很多细节需要实现。思路上和Word
Ladder是比较类似的,但是因为是要求出所有路径,仅仅保存路径长度是不够的,而且这里还有更多的问题,那就是为了得到所有路径,不是每个结点访问一次就可以标记为visited了,因为有些访问过的结点也会是别的路径上的结点,所以访问的集合要进行回溯(也就是标记回未访问)。所以时间上不再是一次广度优先搜索的复杂度了,取决于结果路径的数量。同样空间上也是相当高的复杂度,因为我们要保存过程中满足的中间路径到某个数据结构中,以便最后可以获取路径,这里我们维护一个HashMap,把一个结点前驱结点都进行保存。
在LeetCode中用Java实现上述算法非常容易超时。为了提高算法效率,需要注意一下两点:
1)在替换String的某一位的字符时,先转换成char数组再操作;
2)如果按照正常的方法从start找end,然后根据这个来构造路径,代价会比较高,因为保存前驱结点容易,而保存后驱结点则比较困难。所以我们在广度优先搜索时反过来先从end找start,最后再根据生成的前驱结点映射从start往end构造路径,这样算法效率会有明显提高。
代码如下:
class StringWithLevel {
String str;
int level;
public StringWithLevel(String str, int level) {
this.str = str;
this.level = level;
}
}
public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
HashSet<String> unvisitedSet = new HashSet<String>();
unvisitedSet.addAll(dict);
unvisitedSet.add(start);
unvisitedSet.remove(end);
Map<String, List<String>> nextMap = new HashMap<String, List<String>>();
for (String e : unvisitedSet) {
nextMap.put(e, new ArrayList<String>());
}
LinkedList<StringWithLevel> queue = new LinkedList<StringWithLevel>();
queue.add(new StringWithLevel(end, 0));
boolean found = false;
int finalLevel = Integer.MAX_VALUE;
int curLevel = 0;
int preLevel = 0;
HashSet<String> visitedCurLevel = new HashSet<String>();
while (!queue.isEmpty()) {
StringWithLevel cur = queue.poll();
String curStr = cur.str;
curLevel = cur.level;
if(found && curLevel > finalLevel) {
break;
}
if (curLevel > preLevel) {
unvisitedSet.removeAll(visitedCurLevel);
}
preLevel = curLevel;
char[] curStrCharArray = curStr.toCharArray();
for (int i = 0; i < curStr.length(); ++i) {
char originalChar = curStrCharArray[i];
boolean foundCurCycle = false;
for (char c = 'a'; c <= 'z'; ++c) {
curStrCharArray[i] = c;
String newStr = new String(curStrCharArray);
if(c != originalChar && unvisitedSet.contains(newStr)) {
nextMap.get(newStr).add(curStr);
if(newStr.equals(start)) {
found = true;
finalLevel = curLevel;
foundCurCycle = true;
break;
}
if(visitedCurLevel.add(newStr)) {
queue.add(new StringWithLevel(newStr, curLevel + 1));
}
}
}
if(foundCurCycle) {
break;
}
curStrCharArray[i] = originalChar;
}
}
if(found) {
ArrayList<String> list = new ArrayList<String>();
list.add(start);
getPaths(start, end, list, finalLevel + 1, nextMap, res);
}
return res;
}
private void getPaths(String cur, String end, ArrayList<String> list, int level, Map<String, List<String>> nextMap, ArrayList<ArrayList<String>> res) {
if(cur.equals(end)){
res.add(new ArrayList<String>(list));
}
else if(level > 0){
List<String> parentsSet = nextMap.get(cur);
for (String parent : parentsSet) {
list.add(parent);
getPaths(parent, end, list, level - 1, nextMap, res);
list.remove(list.size() - 1);
}
}
}
这道题目实现中有很多细节和技巧,个人觉得如果在面试中遇到很难做到完整,而且考核的算法思想也不是很精妙,更多的是繁琐的操作。在面试中时间上花费太大,也不是很合适,大家主要还是了解一下思路哈。
分享到:
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
博士力士乐专用软件,编程工具,设定工具。官网上下载不到,只有找力士乐客服才能弄到。
FANUC LADDER-III V8.9最新升级包
FANUC LADDER-III V8.7 PMC编程软件
Ladder with authenticating user 1. 实现spring security的四种方法 1. 全部利用配置文件 不使用数据库,全部信息写在配置文件中,如拦截的URL及对应权限,指定用户名、密码和对应权限 2. 数据库+配置文件 数据库...
FANUC LADDER-III V8.0最新版 FANUC梯形图软件最新版
FANUC LADDER-III V7.5附带序列号汉化包,点击文件夹内的 FL3AutoRun.exe 即可打开安装程序,安装过程中“Serial”表示需要输入序列号,安装完后进入汉化包文件夹,阅读 Readme.txt按照说明即可免费将软件汉化
FANUC LADDER-III 6.9 汉化包
日本Fanuc PMC 梯形图软件 FAPT LADDER-IIIv4.60 .part2rar,日本Fanuc PMC 梯形图软件 FAPT LADDER-IIIv4.60 .part2
5.7 6.3可用 安装时注意选择软件安装文件夹
pta天梯赛题单ladder-race-question-master.zip
FANUC梯形图软件FANUC LADDER-III V7.5
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
Fanuc_梯形图软件_FAPT_LADDER-IIIv5.0
FANUC 系统梯图编辑软件,LADDER-3 V5.7 的汉化补丁,新春双语版,能进行中英文的转换!
FANUC LADDER-III如何读取发那科机器人PMC程序以及保存到电脑.pptx
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
力扣 Python 解决方案Leetcode 是准备技术编码面试的...特别案例: Word Ladder II,我的 AC 代码比这个 repo 中的代码慢得多。 但是这个 repo 中的一个得到了 TLE,不知道为什么。 任何想法都将受到高度赞赏。 谢谢!
LADDERii_MANUAL,FANUC 工具機的控制器PMC編程說明手冊,可提供編程者規劃程序時使用。