public int ladderLength(String start, String end, Set<String> dict) {
        // write your code here
        if (dict == null) return 0;
        if (start.equals(end)) return 1;

        dict.add(start);
        dict.add(end);

        Set<String> set = new HashSet<>();
        Queue<String> q = new LinkedList<>();
        set.add(start);
        q.add(start);
        int len = 1;

        while (!q.isEmpty()) {
            len++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String s = q.poll();
                for (String word : getNextWord(s, dict)) {
                    if (set.contains(word)) continue;
                    if (word.equals(end)) return len;
                    q.offer(word);
                    set.add(word);
                }
            }
        }
        return 0;
    }
    public String replace(String s, int index, char c) {
        char[] x = s.toCharArray();
            x[index] = c;
        return new String(x);
    }
    public ArrayList<String> getNextWord(String s, Set<String> dict) {
        ArrayList<String> res = new ArrayList<>();
        for (char c = 'a'; c < 'z'; c++) {
            for (int i = 0; i < s.length(); i++) {
                if (c == s.charAt(i)) continue;
                String nextWord = replace(s, i, c);
                if (dict.contains(nextWord)) {
                    res.add(nextWord);
                }
            }
        }
        return res;
    }