@@ -0,0 +1,1919 @@
+/* P0006%0A *%0A * Word Ladder%0A * Given two words (start and end), and a dictionary, find the length of%0A * shortest transformation sequence from start to end, such that%0A *%0A * 1) Olny one letter can be changed at a time.%0A * 2) Each intermediate word must exist in the dictionary.%0A *%0A * For example,%0A * %0A * Given:%0A * start = %22hit%22%0A * end = %22cog%22%0A * dict = %5B%22hot%22, %22dot%22, %22dog%22, %22lot%22, %22log%22%5D%0A * As one shortest transformation is %22hit%22 -%3E %22hot%22 -%3E %22dot%22 -%3E %22dot%22 -%3E %22cog%22,%0A * return its length 5.%0A *%0A * Note:%0A * Return 0 if there is no such transformation sequence.%0A * All words have the same length.%0A * All words contain only lowercase alphabetic characters.%0A * */%0A%0Aimport java.util.HashSet;%0Aimport java.util.Arrays;%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0A%0Apublic class P0006 %7B%0A%0A  @SuppressWarnings(%22unchecked%22)%0A  public static int wordLadder(String start, String end, HashSet%3CString%3E dict) %7B%0A    int res = 0;%0A%0A    // use a copy of the dictionary%0A    dict = (HashSet%3CString%3E)dict.clone();%0A%0A    Queue%3CString%3E queue = new LinkedList%3CString%3E();%0A    queue.offer(start);%0A%0A    int level = 0;%0A    while (queue.size() %3E 0) %7B%0A      String current = queue.poll();%0A      for (String cand : dict) %7B%0A        if (isValidTrans(current, cand)) %7B%0A        %7D%0A      %7D%0A    %7D%0A%0A    return res;%0A  %7D%0A%0A  private static boolean isValidTrans(String src, String tgt) %7B%0A    int len = src.length();%0A%0A    int mismatchCount = 0;%0A    for (int i = 0; i %3C len; i++) %7B%0A      if (src.charAt(i) != tgt.charAt(i))%0A        mismatchCount++;%0A%0A      if (mismatchCount %3E 1)%0A        return false;%0A    %7D%0A%0A    return mismatchCount == 1;%0A  %7D%0A%0A  public static void main(String%5B%5D args) %7B%0A    String start = %22hit%22, end = %22cog%22;%0A    String%5B%5D dictArray = new String%5B%5D%7B%22hot%22, %22dot%22, %22dog%22, %22lot%22, %22log%22%7D;%0A    HashSet%3CString%3E dict = new HashSet%3CString%3E(Arrays.asList(dictArray));%0A%0A    int res = P0006.wordLadder(start, end, dict);%0A%0A    System.out.println(res);%0A  %7D%0A%7D%0A

save the progress of P0006