/*

* @lc app=leetcode id=127 lang=java

*

* [127] Word Ladder

*/

class Solution {

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

if (!wordList.contains(endWord)) return 0;

int level = 1;

Set<String> set = new HashSet<>();

for(String word: wordList){

set.add(word);

}

Queue<String> queue = new LinkedList<>();

queue.offer(beginWord);

while(!queue.isEmpty()){

int size = queue.size();

for(int i = 0; i < size; i++){

String tmpWord = queue.poll();

char[] array = tmpWord.toCharArray();

for(int j = 0; j < array.length; j++){

char c = array[j];

for(char k = 'a'; k <= 'z'; k++){

array[j] = k;

String newWord = String.valueOf(array);

if(k != c &&set.contains(newWord)){

queue.offer(newWord);

set.remove(newWord);

if(newWord.equals(endWord)){

return ++level;

}

}

}

array[j] = c;

}

}

level++;

}

return 0;

}

}