首页 > 搜索 > BFS搜索 > hdu 2360 Word Ladder-BFS-[解题报告]java
2014
01-05

hdu 2360 Word Ladder-BFS-[解题报告]java

Word Ladder

问题描述 :

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) {
			dict.add(s);
		}
		String start = "hit";
		String end = "cog";
		Solution solution = new Solution();
		System.out.println(solution.ladderLength(start, end, dict));
	}
	
	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) {
	               list.add(t);
	           }              
	       }
	   }
	   // 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;
			   visited.add(s);
			   nextLevel.addAll(graph.get(s));
		   }
		   firstLevel.clear();
		   for (String t : nextLevel) {
			   if (!visited.contains(t)) {
				   firstLevel.add(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;
	}
}

解题转自:http://blog.csdn.net/beiyetengqing/article/details/8580577


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