/*
Using BFS(queue) to approach this question

- use a HashSet to convert the wordList into a set
- use a Queue q to watch the level of the graph

while q is not empty:
    for each word in the queue
        for each char of the word, we try a~z and see whether hashset contains it or not
            if hashset contains it and if the word is the end word, we just return level +1; otherwise, we put it into queue and iterate.

    after exhaustive a level of queue, level++

return 0;

*/



public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        HashSet<String> hs = new HashSet<String>();
        for (String ele:wordList) {
            hs.add(ele);
        }

        if (!hs.contains(endWord)) {
            return 0;
        }

        Queue<String> q = new LinkedList<String>();
        q.add(beginWord);
        int level = 1;

        while(!q.isEmpty()) {
            int qSize = q.size();
            for (int i=0; i<qSize; i++){
                String cur = q.poll();
                char[] arr = cur.toCharArray();

                for(int j=0; j<arr.length; j++){
                    char original = arr[j];
                    for (char c='a'; c<='z'; c++) {
                        if (arr[j]==c) {
                            continue;
                        }
                        //String original = String.valueOf(arr);
                        arr[j] = c;
                        String test = String.valueOf(arr);
                        if (hs.contains(test)) {
                            if (test.equals(endWord)) {
                                return level+1;
                            }
                            q.add(test);
                            hs.remove(test);
                        }
                        //arr = original.toCharArray();
                    }
                    arr[j] = original;

                }
            }
            level++;
        }

        return 0;




    }
}