127. Word Ladder

/*
Time Complexity: O(N * L)
Space Complexity: O(N * L)

N = Number of words in the wordList
L = Average length of the words in the wordList.

Questions to be asked to Interviewer:
1. If word ladder is "hot" -> "hit" .. is the result 1 or 2.
2. Is end word always part of wordList.
*/
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> beginSet = new HashSet<String>();
        HashSet<String> endSet = new HashSet<String>();
        HashSet<String> visitedSet = new HashSet<String>();
        HashSet<String> wordListSet = new HashSet<String>();

        for (String word : wordList) {
            wordListSet.add(word);
        }

        beginSet.add(beginWord);

        if (wordListSet.contains(endWord)) {
            endSet.add(endWord);
        } else {
            return 0;
        }

        int ladderLength = 1;
        int wordLength = beginWord.length();

        while (!beginSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                HashSet<String> swapSet = beginSet;
                beginSet = endSet;
                endSet = swapSet;
            }

            HashSet<String> tempSet = new HashSet<String>();

            for (String word : beginSet) {
                char[] wordCharArray = word.toCharArray();
                for (int i = 0; i < wordLength; i++) {
                    char old = wordCharArray[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        wordCharArray[i] = c;
                        String target = new String(wordCharArray);

                        if (endSet.contains(target)) {
                            return ladderLength + 1;
                        }

                        if (!visitedSet.contains(target) && wordListSet.contains(target)) {
                            visitedSet.add(target);
                            tempSet.add(target);
                        }
                    }
                    wordCharArray[i] = old;
                }
            }

            beginSet = tempSet;
            ladderLength++;
        }

        return 0;
    }
}