public class Solution {

  // use BFS to solve

  // in every level of BFS searching,

  // we find the word that replaced by one char and also in the dict without have seen before

  // data structure: seen(HashSet), cur(Queue)

  // assume that the wordList is not null, case insensitive, no duplicate, every word is non-empty

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

    // Write your solution here

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

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

    seen.add(beginWord);

    cur.offer(beginWord);

    int cnt = 1;

    while(cur.size()>0){

      cnt++;

      int size = cur.size();

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

        String todo = cur.poll();

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

          List<String> changed= getQualified(todo, j, wordList, seen);

          for(String s: changed){

            if(String.valueOf(s)==String.valueOf(endWord)){

              return cnt;

            }else{

              cur.offer(s);

              seen.add(s);

            }

          }

        }

      }

    }

    return 0;

  }

  private List<String> getQualified(String from, int ignore, List<String> wordList, HashSet<String> seen){

    List<String> res = new ArrayList<>();

    for(String s: wordList){

      int flag = 0;

      for(int i=0; i<from.length(); i++){

        if(i!=ignore && from.charAt(i)!=s.charAt(i)){

          flag=1;

        }

      }

      if(flag==0 && !seen.contains(s)){

        res.add(s);

      }

    }

    return res;

  }

}