一亩三分地论坛

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

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

[学Java/C#] 个人感觉思路比较清晰的word ladder II解法 by Java, 欢迎大家来讨论其他更好方法

[复制链接] |试试Instant~ |关注本帖
MYcolting 发表于 2014-11-8 13:39:21 | 显示全部楼层 |阅读模式

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

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

x
  1. public class Solution {
  2.     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
  3.     // Start typing your Java solution below
  4.     // DO NOT write main() function
  5.     // method would be similar, except that, we need to store the path
  6.     // in addition, if we get the result, we didn't stop until we finish
  7.     // all the path of the same length
  8.     // visited map the string to the list of its ancestor
  9.     HashMap<String, HashSet<String>> visited=new HashMap<String, HashSet<String>>();
  10.     HashMap<String, Integer> level=new HashMap<String, Integer>();
  11.     LinkedList<String> queue=new LinkedList<String>();
  12.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
  13.     if (start==null || end==null || start.length()!=end.length())
  14.     {
  15.         return result;
  16.     }
  17.     // we also need to store the path for the start
  18.     HashSet<String> path=new HashSet<String>();
  19.     // we record the minimal length we get
  20.     int min_length=Integer.MAX_VALUE;
  21.     visited.put(start, path);
  22.     level.put(start, 1);
  23.     queue.add(start);
  24.     while(!queue.isEmpty())
  25.     {
  26.         String s=queue.remove();
  27.         char[] chars=s.toCharArray();
  28.         for (int i=0; i<s.length(); i++)
  29.         {
  30.             char old=chars[i];
  31.             for (char c='a'; c<='z'; c++)
  32.             {
  33.                 chars[i]=c;
  34.                 String s2=new String(chars);
  35.                 // avoid circle
  36.                 // check whether it is in the dictionary
  37.                 // we only add the string which is nearer to the start
  38.                 if (dict.contains(s2) && (!level.containsKey(s2) || (level.containsKey(s2) && level.get(s2)>level.get(s))))
  39.                 {
  40.                     // we update the ancestor of the string
  41.                     if (visited.containsKey(s2))
  42.                     {
  43.                         visited.get(s2).add(s);
  44.                     }
  45.                     else
  46.                     {
  47.                         // we haven't seen this node before
  48.                         // thus we add it to the queue and also its ancestor
  49.                         path=new HashSet<String>();
  50.                         path.add(s);
  51.                         visited.put(s2, path);
  52.                         level.put(s2, level.get(s)+1);
  53.                         queue.add(s2);
  54.                     }
  55.                 }
  56.                 if (s2.equals(end))
  57.                 {
  58.                     // we found it
  59.                     // we will use back trace to found its path to start
  60.                     if (level.get(s)<min_length)
  61.                     {
  62.                         // it is shortest path
  63.                         ArrayList<String> entry=new ArrayList<String>();
  64.                         entry.add(end);
  65.                         result.addAll(back_trace(s, visited, entry));
  66.                         min_length=level.get(s)+1;
  67.                     }
  68.                     else
  69.                     {
  70.                         // ok, all the remaining path should be longer
  71.                         break;
  72.                     }
  73.                 }
  74.             }
  75.             chars[i]=old;
  76.         }
  77.     }
  78.     return result;
  79. }

  80. private ArrayList<ArrayList<String>> back_trace(String end, HashMap<String, HashSet<String>> visited, ArrayList<String> path)
  81. {
  82.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
  83.     ArrayList<String> entry=new ArrayList<String>(path);
  84.     entry.add(0, end);
  85.     if (visited.get(end).size()<1)
  86.     {
  87.         result.add(entry);
  88.         return result;
  89.     }
  90.     for (String str: visited.get(end))
  91.     {
  92.         result.addAll(back_trace(str, visited, entry));
  93.     }
  94.     return result;
  95. }
  96. }
复制代码
readman 发表于 2014-11-9 07:57:59 | 显示全部楼层
速度还不错. 刚试了试..思路嘛..不是原创吧..以前见过
回复 支持 反对

使用道具 举报

toplee_xd 发表于 2014-11-21 18:03:39 | 显示全部楼层
如果你 写一个 graph 的类来做这题更加清楚易懂。。。。这题考察的关键就是graph search。。
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-2-22 12:54:05 | 显示全部楼层
这道题有没有文字讲解版本的。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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