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

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2014-12-01 11:10:24

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
*************************************************************************
分析:
        每一层查找一步可达的item,并保存;
        每一层访问完层数加1。

*************************************************************************
注意事项:
        何时停止,越早越好
        何时将访问过的点保存,越早越好
*************************************************************************

点击(此处)折叠或打开

  1.     public int ladderLength(String start, String end, Set<String> dict) {
  2.         if (start.length() != end.length()) return 0;
  3.         Queue<String> q = new LinkedList<String>();
  4.         Queue<String> qNext = new LinkedList<String>();
  5.         Queue<String> qTemp = null;
  6.         Set<String> set = new HashSet<String>();
  7.         int count = 1;
  8.         q.add(start);
  9.         while (!q.isEmpty()) {
  10.             String item = q.poll();
  11.             //set.add(item);
  12.             char []cs = item.toCharArray();
  13.             for (int i = 0; i < item.length(); i++) {
  14.                 
  15.                 // change one char
  16.                 for (char c = 'a'; c <= 'z'; c++) {
  17.                     cs[i] = c;
  18.                     String temp = new String(cs);
  19.                     if (temp.equals(end)) return count + 1;
  20.                     // not visit yet
  21.                     if (dict.contains(temp) && !set.contains(temp)) {
  22.                         qNext.add(temp);
  23.                         set.add(temp);
  24.                     }    
  25.                     cs[i] = item.charAt(i);
  26.                 }
  27.             }
  28.             if (q.isEmpty()) {
  29.                 qTemp = qNext;
  30.                 qNext = q;
  31.                 q = qTemp;
  32.                 count++;
  33.             }
  34.         }
  35.         return 0;
  36.     }

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

登录 注册