- 浏览: 595979 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
月光杯:
问题解决了吗?
Exceptions in HDFS -
iostreamin:
神,好厉害,这是我找到的唯一可以ac的Java代码,厉害。
[leetcode] word ladder II -
standalone:
One answer I agree with:引用Whene ...
How many string objects are created? -
DiaoCow:
不错!,一开始对这些确实容易犯迷糊
erlang中的冒号 分号 和 句号 -
standalone:
Exception in thread "main& ...
one java interview question
Q: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
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.
http://leetcode.com/onlinejudge#question_127
Solution:
Much more easier than word ladder 2. BFS search.
Only one letter can be changed at a time
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.
http://leetcode.com/onlinejudge#question_127
Solution:
Much more easier than word ladder 2. BFS search.
public class Solution { public int ladderLength(String start, String end, HashSet<String> dict) { // Start typing your Java solution below // DO NOT write main() function dict.add(start); dict.add(end); // calcualte ajacent matrix HashMap<String, ArrayList<String>> adj = new HashMap<String, ArrayList<String>>(); for(String str : dict){ char [] chars = str.toCharArray(); for(int i=0;i<start.length();i++){ char old = chars[i]; for(char c = 'a' ; c <= 'z'; c++){ if(c == old) continue; chars[i] = c; String newstr = new String(chars); if(dict.contains(newstr)){ ArrayList<String> neighbours = adj.get(str); if(neighbours == null){ neighbours = new ArrayList<String>(); neighbours.add(newstr); adj.put(str, neighbours); }else { neighbours.add(newstr); } } } chars[i] = old; } } HashSet<String> visited = new HashSet<String>(); LinkedList<Node> queue = new LinkedList<Node>(); queue.add(new Node(1, start)); visited.add(start); int pathLen = 0; while(!queue.isEmpty()){ Node n = queue.pollFirst(); if(n.str.equals(end)){ pathLen = n.level; break; }else { ArrayList<String> neighbours = adj.get(n.str); if(neighbours == null || neighbours.isEmpty()) continue; for(String s : neighbours){ if(! visited.contains(s)){ Node p = new Node(n.level+1, s); queue.add(p); visited.add(s); } } } } return pathLen; } public class Node { public int level; public String str; Node(int l, String s){ str = s; level = l; } } }
发表评论
-
ssl 与 java 实例
2014-01-27 10:10 750http://www.iteye.com/topic/1125 ... -
Java NIO
2014-01-10 21:28 703看了这个java nio的教程,明白了什么是Selector. ... -
再谈Java的wait(), sleep(), notify()和notifyAll()
2013-07-25 10:59 1872一段时间不用java,这些概念就全混淆了,有必要彻底澄清一下, ... -
Why singleton is anti-pattern?
2013-07-03 10:12 873OO Test Other reasons? -
How to generate the serialVersionUID when you implement Serializable interface,j
2013-07-01 10:52 919http://docs.oracle.com/javase/6 ... -
Java Override的两个问题
2013-06-01 11:40 9261: 如果子类中的方法的参数是父类的方法的子类型,那么算不算o ... -
Java常用类API统计
2013-06-01 11:35 0String charAt(int) compareTo( ... -
How many string objects are created?
2013-06-01 10:18 1315This is a very common java inte ... -
使用Java的DelayQueue容易碰到的一个坑
2013-05-27 17:32 6671今天不忙,学习一下java.util.concurrent.D ... -
[leetcode] Decode ways
2013-05-02 21:47 1393http://leetcode.com/onlinejudge ... -
[leetcode] Balanced Binary Tree
2013-04-28 14:08 1563Check if a binary tree is balan ... -
[leetcode] find median of two sorted arrays
2013-04-26 10:55 1437http://leetcode.com/onlinejudge ... -
[leetcode] sqrt(x)
2013-04-15 07:44 2431I have talked about this questi ... -
[leetcode] word ladder II
2013-04-15 07:35 11646http://leetcode.com/onlinejudge ... -
[leetcode] Count and Say
2013-04-12 14:05 2241http://leetcode.com/onlinejudge ... -
Date/Time处理函数总结 [To Do]
2013-04-12 10:46 643几种我所用到的用来处理日期,时间的函数总结。 Perl 1 ... -
[leetcode] Palindrome Partition
2013-04-12 10:25 1308http://leetcode.com/onlinejudge ... -
[leetcode] Palindrome Partitioning II
2013-04-11 16:45 1495http://leetcode.com/onlinejudge ... -
Profiling your Java code using Spring
2013-03-05 15:02 664Quite good article!!! http://w ... -
Java的Generics的几点限制
2012-12-28 15:00 4709参见 http://docs.oracle.com/ ...
相关推荐
126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】
经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
自己做leecode题目的总结,做个分享从事服务端开发,少不了要接触网络编程。epoll作为linux下高性能网络服务器的必备技术至关重要,nginx、redis、skynet和大部分游戏服务器都使用到这一多路复用技术。...
leetcode刷题, 直接用leetcode的分类方式.
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
这份文档列出了leetcode几乎所有题目(大约134题)的分类以及难度指示,是刷leetcode的必备良品。现在leetcode总的题目数已经达到150题,所以有部分题目没有包含在这个文档中,但是——足够了。po主刷leetcode的时候...
leetcode高频面试笔试题150+道,亲身总结。
LeetCode面试笔试题
LeetCode 刷题笔记
(C++)LeetCode刷题题解答案