一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 642|回复: 2
收起左侧

[算法题] Word Ladder II几个地方看不太懂请教一下。。。

[复制链接] |试试Instant~ |关注本帖
zh355245849 发表于 2015-7-5 22:56:14 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
  1. class Node {
  2.     public int level = 1;
  3.     public Node previous;
  4.     public String str;
  5.     public Node(int l, Node n, String s) {
  6.         level = l;
  7.         previous = n;
  8.         str = s;
  9.     }
  10. }
  11. public class Solution {
  12.     public List<List<String>> findLadders(String start, String end, Set<String> dict) {
  13.         HashMap<String,HashSet<String>> neighbours = new HashMap<String,HashSet<String>>();
  14.         dict.add(start);
  15.         dict.add(end);
  16.         for(String str : dict)
  17.             buildGraph(neighbours, str, dict);
  18.         List<List<String>> res = new ArrayList<List<String>>();
  19.         LinkedList<Node> queue = new LinkedList<Node>();
  20.         queue.add(new Node(1, null, start));
  21.         int previousLevel = 0;
  22.         HashMap<String,Integer> visited = new HashMap<String,Integer>();
  23.         while(!queue.isEmpty()) {
  24.             Node n = queue.poll();
  25.             if(end.equals(n.str)) {
  26.                 if(previousLevel ==0 || n.level == previousLevel) {
  27.                     previousLevel = n.level;
  28.                     findPath(n, res);
  29.                 }
  30.                 else
  31.                     break;
  32.             } else {
  33.                 HashSet<String> set = neighbours.get(n.str);
  34.                 if(set == null || set.isEmpty())
  35.                     continue;
  36.               //  ArrayList<String> toRemove = new ArrayList<String>();
  37.                 for(String s: set) {
  38.                     if(visited.containsKey(s)) {
  39.                     int occurLevel = visited.get(s);
  40.                     if(n.level+1 > occurLevel) {
  41.                         neighbours.get(s).remove(n.str);
  42.                      //   toRemove.add(s);
  43.                         continue;
  44.                     }
  45.                     }
  46.                     visited.put(s, n.level + 1);
  47.                     queue.add(new Node(n.level + 1, n, s));
  48.                     if(neighbours.containsKey(s))
  49.                         neighbours.get(s).remove(n.str);
  50.                 }
  51.                 //for(String s: toRemove) {
  52.                   //  set.remove(s);
  53.                // }
  54.             }
  55.         }
  56.         return res;
  57.     }
  58.     public void buildGraph(HashMap<String,HashSet<String>> neighbours, String str, Set<String> dict) {
  59.        // int level = 1, next = 0, cur = 1;
  60.         int len = str.length();
  61.         char[] wordUnit = str.toCharArray();
  62.         for(int i = 0; i < len; i++) {
  63.             char c = wordUnit[i];
  64.             for(char j = 'a'; j <='z'; j++) {
  65.                 if(c == j)   //跑到和自身相同的字符串跳过去!
  66.                     continue;
  67.                 wordUnit[i] = j;
  68.                 String newstr = new String(wordUnit);
  69.                 if(dict.contains(newstr)) {
  70.                     HashSet<String> set = neighbours.get(str);
  71.                     if(set != null)
  72.                         set.add(newstr);
  73.                     else {
  74.                         HashSet<String> newset = new HashSet<String>();
  75.                         newset.add(newstr);
  76.                         neighbours.put(str,newset);
  77.                     }
  78.                 }
  79.             }
  80.             wordUnit[i] = c;
  81.         }
  82.     }
  83.     public void findPath(Node n, List<List<String>> result) {
  84.         ArrayList<String> path = new ArrayList<String>();
  85.         Node p = n;
  86.         while(p != null) {
  87.             path.add(0, p.str);
  88.             p = p.previous;
  89.         }
  90.         result.add(path);
  91.     }
  92. }
复制代码
FindLadders中的if(previousLevel ==0 || n.level == previousLevel) {
                    previousLevel = n.level;
                    findPath(n, res);
                }和if(n.level+1 > occurLevel) {
                        neighbours.get(s).remove(n.str);是在判断什么哦。。。谢谢了!
glaciersilent 发表于 2015-7-6 03:24:16 | 显示全部楼层
这算是一个比较繁琐的BFS题 而且我觉得这个代码写得稍微有点复杂。。这几句我也没太看懂。。就稍微说说我对这题的理解。 这题跟word ladder I的不同就在于,在I题中每一次BFS的时候如果一个word1变化出的所有其他word2中有已经出现过的就直接忽略 因为我们要找的是最短的ladder的长度所以不能走回头路。而word ladderII要找出所有的path,那就意味着如果在某一层word1变化出的word2们中如果有已经出现过的,这时候不能直接丢掉,而是要检查如果这个重复出现的word2正好已经出现在了word1的下一层中 那么假设是某个word3在word1的同层中向下变化出了word2 那么从最开始的word到word2的变化path就是从原始词word经word1和word3变化到word2的path的并集

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-6 04:39:29 | 显示全部楼层
本帖最后由 handsomecool 于 2015-7-6 04:41 编辑

FindLadders中的if(previousLevel ==0 || n.level == previousLevel)  {...}到达最后一个单词的时候要检查是否把这个path放进结果中,如果x步找到了最后一个单词, 那x+1步才找到单词的path就不要放进结果中了。因为最外面的大while loop的condition是!queue.empty(),没办法及时终止,所以他查level来判断当前还是不是最短path。 previousLevel==0 则对应的是第一次找到path的情况。

if(n.level+1 > occurLevel)        neighbours.get(s).remove(n.str);
这个就是看如果这个单词在这轮之前已经visit过了,那就删掉,因为如果在后一轮又visit同一个单词那一定是比最快路线慢了一步。


我也觉得这个code整体写复杂了,有更简洁的写法。 另外一开始建Neighbors我也觉得没必要,况且字典可能很大,不如直接查当前单词换一个字母是否在字典里快。




评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 19:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表