import javafx.util.Pair;
import org.testng.annotations.Test;

import java.util.*;
import static org.testng.Assert.*;

public class Sol {

  static Set<Map<Integer, Integer>> indexPointers(String s) {
    Set<Map<Integer, Integer>> result = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
      Map<Integer, Integer> indexPointer = new TreeMap<Integer, Integer>();
      for (int j = 0; j < s.length(); j++) {
        if (j != i) {
          indexPointer.put(j, s.codePointAt(j));
        }
      }
      result.add(indexPointer);
    }
    return result;
  }

  public static boolean hasPath(List<String> words, String first, String last) {
    Map<Map<Integer, Integer>, Set<String>> index = new HashMap<>();

    Set<String> wordsSet = new HashSet<>(words);
    if (!wordsSet.contains(first)) return false;
    if (!wordsSet.contains(last)) return false;

    for (String word : words) {
      for (Map<Integer, Integer> indexPointer : indexPointers(word)) {
        Set<String> indexWords = index.getOrDefault(indexPointer, new HashSet<>());
        indexWords.add(word);
        index.put(indexPointer, indexWords);
      }
    }

    Deque<String> found = new LinkedList<>();
    found.addFirst(first);

    while (found.size() > 0) {
      String word = found.removeFirst();

      wordsSet.remove(word);
      for (Map<Integer, Integer> indexPointer : indexPointers(word)) {
        Set<String> nextWords = index.get(indexPointer);
        for (String nextWord : nextWords) {
          if (nextWord.equals(last)) return true;
          if (wordsSet.contains(nextWord)) {
            found.addLast(nextWord);
          }
        }
      }
    }

    return false;
  }

  static int editDistance(String s1, String s2) {
    int result = 0;
    for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
      result += s1.codePointAt(i) == s2.codePointAt(i) ? 0 : 1;
    }
    return result;
  }

  public static int hasPath2(List<String> words, String first, String last) {
    Set<String> wordsSet = new HashSet<>(words);
    if (!wordsSet.contains(first)) return -1;
    if (!wordsSet.contains(last)) return -1;

    Deque<Pair<String, Integer>> found = new LinkedList<>();
    found.addFirst(new Pair(first, 0));

    while (found.size() > 0) {
      Pair<String, Integer> elem = found.removeFirst();
      String word = elem.getKey();
      Integer distance = elem.getValue();
      wordsSet.remove(word);
      for (String next : wordsSet) {
        if (editDistance(word, next) == 1) {
          if (next.equals(last)) return distance + 1;
          found.addLast(new Pair<>(next, distance + 1));
        }
      }
    }

    return -1;
  }

  @Test
  public static void checkHasPath() {
    List<String> dict = Arrays.asList(
        "BARE",
        "CARE",
        "CASE",
        "CASK",
        "BASK",
        "RATE",
        "MATE",
        "MANE",
        "BANE",
        "BONE",
        "XYZF"
    );
    assertTrue(hasPath(dict, "BARE", "BASK"));
//    assertTrue(hasPath2(dict, "BARE", "BASK"));
    assertTrue(hasPath(dict, "BASK", "BARE"));
    assertEquals(hasPath2(dict, "BASK", "BARE"), 4);
    assertFalse(hasPath(dict, "BARE", "XYZF"));
//    assertFalse(hasPath2(dict, "BARE", "XYZF"));

  }

}