content: package question127;
  
  import java.util.*;
  
  public class Solution1 {
      class LevelWord {
          String word;
          int level;
  
          public LevelWord(String word, int level) {
              this.word = word;
              this.level = level;
          }
  
      }
  
      public int ladderLength(String beginWord, String endWord, List<String> wordList) {
          int end = wordList.indexOf(endWord);
          if (end == -1) {
              return 0;
          }
          if (!wordList.contains(beginWord)) {
              wordList.add(beginWord);
          }
          boolean[][] nextWords = new boolean[wordList.size()][wordList.size()];
          HashMap<String, Boolean> visited = new HashMap<>();
          for (int i = 0; i < wordList.size(); i++) {
              for (int j = 0; j < i; j++) {
                  if (hasPath(wordList.get(i).toCharArray(), wordList.get(j).toCharArray())) {
                      nextWords[i][j] = nextWords[j][i] = true;
                  }
              }
              visited.put(wordList.get(i), false);
          }
          Queue<LevelWord> queue = new LinkedList<>();
          queue.add(new LevelWord(beginWord, 0));
          visited.put(beginWord, true);
          while (!queue.isEmpty()) {
              LevelWord temp = queue.poll();
              if (temp.word.equals(endWord)) {
                  return temp.level + 1;
              }
              List<String> nextWord = new ArrayList<>();
              int n = wordList.indexOf(temp.word);
              for (int i = 0; i < nextWords[n].length; i++) {
                  if (nextWords[n][i]) {
                      nextWord.add(wordList.get(i));
                  }
              }
              for (int i = 0; i < nextWord.size(); i++) {
                  String nextTemp = nextWord.get(i);
                  if (!visited.get(nextTemp)) {
                      queue.add(new LevelWord(nextTemp, temp.level + 1));
                      visited.put(nextTemp, true);
                  }
              }
          }
          return 0;
      }
  
      private boolean hasPath(char[] arr1, char[] arr2) {
          int diff = 0;
          for (int i = 0; i < arr1.length; i++) {
              if (arr1[i] != arr2[i]) {
                  diff++;
              }
          }
          if (diff == 1) {
              return true;
          }
          return false;
      }
  }
  
  