LeetCode four

leet

package com.westudio.java;

import java.util.*;

public class LeetCodeFour {

    private static int ladderLength(String start, String end, Set<String> dict) {
        if (start == null || end == null ||
                start.equals(end) || start.length() != end.length()) {
            return -1;
        }

        if (isOneWordDiff(start, end)) {
            return 1;
        }

        Queue<String> queue = new LinkedList<String>();
        HashMap<String, Integer> dist = new HashMap<String, Integer>();

        queue.add(start);
        dist.put(start, 1);

        while (!queue.isEmpty()) {
            String head = queue.poll();

            int d = dist.get(head);

            for (int i = 0; i < head.length(); i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    if (head.charAt(i) == c)
                        continue;

                    StringBuilder sb = new StringBuilder(head);
                    sb.setCharAt(i, c);

                    if (sb.toString().equals(end)) {
                        return d;
                    }

                    if (dict.contains(sb.toString()) && !dist.containsKey(sb.toString())) {
                        queue.add(sb.toString());
                        dist.put(sb.toString(), d + 1);
                    }
                }
            }
        }

        return -1;
    }

    /**
     * start and end should have same length
     * @param start
     * @param end
     * @return true if just one word different other false
     */
    private static boolean isOneWordDiff(String start, String end) {
        int diff = 0;

        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) != end.charAt(i)) {
                diff ++;
            }

            if (diff >= 2)
                return false;
        }

        return diff == 1;
    }

    public static void main(String[] args) {

        String start = "hit";
        String end = "cog";
        Set<String> dict = new HashSet<String>();
        dict.add("hot");
        dict.add("dot");
        dict.add("dog");
        dict.add("lot");
        dict.add("log");
        System.out.println(ladderLength(start, end, dict));
    }
}