public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
	if (start == null || end == null || dict == null
				|| start.length() != end.length()) {
			return 0;
		}
		if (oneDiff(start, end)) {

			return 2;
		}
		return helper(start, end, dict, 2);

	}

	public boolean oneDiff(String left, String right) {
		int sameNumber = 0;
		if (left == null || right == null) {
			return false;
		}
		if (left.length() != right.length()) {
			return false;
		}
		for (int i = 0; i < left.length(); i++) {
			if (left.charAt(i) == right.charAt(i)) {
				sameNumber++;
			}
		}
		if (sameNumber == left.length() - 1) {
			return true;
		}
		return false;
	}

	public int helper(String start, String end, Set<String> dict, int level) {
		Queue<String> queue = new LinkedList<String>();
		queue.offer(start);
		HashMap<String,Integer> route = new HashMap<String,Integer>();
		route.put(start,0);
		while (!queue.isEmpty()) {
			int qSize = queue.size();
			for (int i = 0; i < qSize; i++) {
				String cur = queue.poll();
				for (int j = 0; j < cur.length(); j++) {
					for (char c = 'a'; c <= 'z'; c++) {
						if (cur.charAt(j) == c) {
							continue;
						}
						StringBuffer sb = new StringBuffer(cur);
						sb.setCharAt(j, c);
						String nowStr = sb.toString();

						if (nowStr.equals(end)) {
							return level++;
						}
						if (dict.contains(nowStr)
								&& !route.containsKey(nowStr)) {
							queue.offer(nowStr);
							route.put(nowStr,0);

						}
					}
				}

			}
			level++;
		}
		return 0;
	}
}

public class Solution {
	public int ladderLength(String start, String end, Set<String> dict) {
		if (start == null || end == null || dict == null
				|| start.length() != end.length()) {
			return 0;
		}
	
		return helper(start, end, dict, 1);

	}

	public int helper(String start, String end, Set<String> dict, int level) {
		Queue<String> queue = new LinkedList<String>();
		queue.offer(start);
		HashMap<String, Integer> route = new HashMap<String, Integer>();
		route.put(start, 1);
		while (!queue.isEmpty()) {
			String cur = queue.poll();
			int curLevel = route.get(cur);

			for (int j = 0; j < cur.length(); j++) {
				for (char c = 'a'; c <= 'z'; c++) {
					if (cur.charAt(j) == c) {
						continue;
					}
					StringBuffer sb = new StringBuffer(cur);
					sb.setCharAt(j, c);
					String nowStr = sb.toString();

					if (nowStr.equals(end)) {
						return ++curLevel;
					}
					if (dict.contains(nowStr) && !route.containsKey(nowStr)) {
						queue.offer(nowStr);
						route.put(nowStr, curLevel + 1);

					}
				}
			}

		}
		return 0;

	}
}