Chinaunix首页 | 论坛 | 博客
  • 博客访问: 106477
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2014-12-01 16:11:08

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. 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.
https://oj.leetcode.com/problems/word-ladder-ii/
**********************************************************************************************************
分析:
    如果根据Word Ladder修改来做的话,逻辑上是正确的,但是运行效率不够。
    综合分析是由于中间生成了很多暂时用不上的List,而且还得遍历这些List。
    对于这种需要输出路径的问题,一般需要先构造一个基本信息,然后根据基本信息直接生成路径。

    -- 调用bfs生成不同的节点在访问并第一次被访问到时的层数。(去重,并可以利用层数信息进行在dfs中快速过滤)
    -- 调用dfs生成路径。
***********************************************************************************************************
代码:

点击(此处)折叠或打开

  1. /////////////////////////////////////////////////////////////////////////////////////////////////
  2.     //记录每个单词所在的层数
  3.     HashMap<String,Integer> path = new HashMap<String,Integer>();
  4.     //bfs生成path
  5.     void bfs(String start, String end, HashSet<String> dict) {
  6.         Queue queue = new LinkedList<String>();
  7.         queue.add(start);
  8.         path.put(start,0);
  9.         String current;
  10.         while(!queue.isEmpty()) {
  11.             current = (String)queue.poll();
  12.             if(current == end) {
  13.                 continue;
  14.             }
  15.             for(int i = 0; i < current.length(); i++) {
  16.                 char[] strCharArr = current.toCharArray();
  17.                 for(char ch = 'a'; ch <= 'z'; ch++) {
  18.                     if(strCharArr[i] == ch) {
  19.                         continue;
  20.                     }
  21.                     strCharArr[i] = ch;
  22.                     String newWord = new String(strCharArr);
  23.                     if(newWord.equals(end) == true || dict.contains(newWord)) {
  24.                         //每个单词在path中只能出现一次,也就是每个单词只能出现在一层中,这样就很巧妙的解决了环的问题。
  25.                         if(path.get(newWord) == null) {
  26.                             int depth = (int)path.get(current);
  27.                             path.put(newWord,depth + 1);
  28.                             queue.add(newWord);
  29.                         }
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.     }
  35.     //从目标单词往回找开始单词,记录所有路径
  36.     void dfs(String start, String end, HashSet<String> dict, ArrayList<String> pathArray, ArrayList<ArrayList<String>> result) {
  37.         //找到了,需要reverse加入的所有单词
  38.         if(start.equals(end) == true) {
  39.             pathArray.add(start);
  40.             Collections.reverse(pathArray);
  41.             result.add(pathArray);
  42.             return;
  43.         }
  44.         if(path.get(start) == null) {
  45.             return;
  46.         }
  47.         pathArray.add(start);
  48.         int nextDepth = (int)path.get(start) - 1;
  49.         for(int i = 0; i < start.length(); i++) {
  50.             char[] strCharArr = start.toCharArray();
  51.             for(char ch = 'a'; ch <= 'z'; ch++) {
  52.                 if(strCharArr[i] == ch) {
  53.                     continue;
  54.                 }
  55.                 strCharArr[i] = ch;
  56.                 String newWord = new String(strCharArr);
  57.                 //只相差一个字母同时这个单词所在的层数也是当前单词的上一层
  58.                 if(path.get(newWord) != null && (path.get(newWord) == nextDepth)) {
  59.                     ArrayList<String> newPathArray = new ArrayList<String>(pathArray);
  60.                     dfs(newWord, end, dict, newPathArray, result);
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     
  66.     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
  67.         ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
  68.         ArrayList<String> path = new ArrayList<String>();
  69.         if(start == null||end == null||start.length() != end.length()) {
  70.             return result;
  71.         }
  72.         //use bfs to get every node's depths
  73.         bfs(start, end, dict);
  74.         
  75.         dfs(end, start, dict, path, result);
  76.         return result;
  77.     }



阅读(382) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册