Word Ladder (Java)

	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.
	Solution:
	Classical BFS question, with same formate with binary tree level traversal, different point is
	how to check valid children(neighbours) and put them into qToPush(next_level queue in BT level traversal)
	public class Solution {
	public int ladderLength(String start, String end, HashSet<String> dict) {
	if (start==null||end==null||dict==null||start.length()==0||start.length()!=end.length()){
	return 0;
	}
	Queue<String> qToOffer=new LinkedList<String>();
	Queue<String> qToPoll=new LinkedList<String>();
	int i=1;
	qToPoll.offer(start);
	while (!qToPoll.isEmpty()||!qToOffer.isEmpty()){
	while(!qToPoll.isEmpty()){
	String current=qToPoll.poll();
	char[] sChars=current.toCharArray();
	for (int j=0; j<sChars.length; j++){
	char original=sChars[j];
	for (char c='a'; c<='z'; c++){
	if (c==sChars[j]){
	continue;
	}
	sChars[j]=c;
	String tempStr=String.copyValueOf(sChars);
	if (tempStr.equals(end)){
	return i+1;
	}
	if (dict.contains(tempStr)){
	qToOffer.offer(tempStr);
	// if not remove tempStr, a loop may happened
	dict.remove(tempStr);
	}
	}
	// don't forget to recover the sChars to orginal sChars
	sChars[j]=original;
	}
	}
	// level++
	i++;
	Queue<String> tempQ=qToPoll;
	qToPoll=qToOffer;
	qToOffer=tempQ;
	}
	return 0;
	}
	}

view raw Word Ladder.java hosted with ❤ by GitHub