2014
01-05

A word ladder is a sequence of words, in which two consecutive words differ by exactly one letter. An example of such a ladder (usually arranged vertically, hence the "ladder" would be: beer, brew, brow, word, down. Note that to get from one word to the next, the letters may be rearranged, and exactly one letter is changed.
For this problem, you will be given a dictionary of distinct words, all of the same length. Your task is to write a program that finds a word ladder of minimal length, such that the first and last word of the ladder have no letters in common.

On the first line an integer t (1<=t <= 100): the number of test cases. Then for each test case:

A line with two space-separated integers n (2 <= n <= 100) and l (1 <= l <= 20): the number of words and their length.

n lines with a word, each consisting of l lowercase letters (a – z).

On the first line an integer t (1<=t <= 100): the number of test cases. Then for each test case:

A line with two space-separated integers n (2 <= n <= 100) and l (1 <= l <= 20): the number of words and their length.

n lines with a word, each consisting of l lowercase letters (a – z).

1
9 3
alt
spy
sea
opt
pea
ape
spa
apt
ale

ale alt apt opt

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.

Idea: create graph and perform BFS.

public class Solution {

public static void main(String[] args) {
HashSet<String> dict = new HashSet<String>();
String[] strDict = {"hot","dot","dog","lot","log"};
for (String s : strDict) {
}
String start = "hit";
String end = "cog";
Solution solution = new Solution();
}

public int ladderLength(String start, String end, HashSet<String> dict) {

//create graph
HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();

graph.put(start, new ArrayList<String>());
graph.put(end, new ArrayList<String>());
for(String d : dict) {
graph.put(d, new ArrayList<String>());
}
for(String s : graph.keySet()) {
ArrayList<String> list = graph.get(s);
for(String t : graph.keySet()) {
if(getDiff(s,t) == 1) {
}
}
}
// use BFS to traverse the node in the graph, we begin with "start"
int step = 0;
HashSet<String> visited = new HashSet<String>();
ArrayList<String> firstLevel = new ArrayList<String>(graph.get(start));

while (firstLevel.size() != 0) {
step++;
ArrayList<String> nextLevel = new ArrayList<String>();
for (String s : firstLevel) {
if (s.equals(end)) return step + 1;
}
firstLevel.clear();
for (String t : nextLevel) {
if (!visited.contains(t)) {
}
}
nextLevel.clear();
}
return 0;
}

public int getDiff(String w1, String w2) {
int count = 0;
for(int i = 0; i < w1.length(); i++) {
if(w1.charAt(i) != w2.charAt(i)) {
count++;
}
}
return count;
}
}

1. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！