Word Ladder

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

Notice

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Below is an algorithm easily to understand with BFS. It also demonstrated another way of tracking levels:loop the queue with it's start size.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

public class Solution { /** * @param start, a string * @param end, a string * @param dict, a set of string * @return an integer */ public int ladderLength(String start, String end, Set<String> dict) { // write your code here Queue<String> queue = new LinkedList<String>(); if(start.equals(end))return 1; queue.offer(start); dict.remove(start); int length = 1; //BFS level traverse while (!queue.isEmpty()) { int count = queue.size();//smart for (int i = 0; i < count; i++){//after loop, it's next level String current = queue.poll(); for (char c = 'a'; c <= 'z'; c++) { for (int j = 0; j < current.length(); j++) { if (c == current.charAt(j)) { continue; } String tmp = replace(current, j, c); if (tmp.equals(end)) {//end condition return length + 1; } if (dict.contains(tmp)){ queue.offer(tmp); dict.remove(tmp); } } } }//if it goes to next level, it means one intermediate word was find length++; } return 0; } private String replace(String s, int index, char c) { char[] chars = s.toCharArray(); chars[index] = c; return new String(chars); } }