class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    unordered_set<string> wordSet{begin(wordList), end(wordList)};
    if (!wordSet.count(endWord))
      return {};

    // {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    unordered_map<string, vector<string>> graph;

    // build graph from beginWord -> endWord
    if (!bfs(beginWord, endWord, wordSet, graph))
      return {};

    vector<vector<string>> ans;

    dfs(graph, beginWord, endWord, {beginWord}, ans);
    return ans;
  }

 private:
  bool bfs(const string& beginWord, const string& endWord,
           unordered_set<string>& wordSet,
           unordered_map<string, vector<string>>& graph) {
    unordered_set<string> currentLevelWords{beginWord};

    while (!currentLevelWords.empty()) {
      for (const string& word : currentLevelWords)
        wordSet.erase(word);
      unordered_set<string> nextLevelWords;
      bool reachEndWord = false;
      for (const string& parent : currentLevelWords) {
        vector<string> children;
        getChildren(parent, wordSet, children);
        for (const string& child : children) {
          if (wordSet.count(child)) {
            nextLevelWords.insert(child);
            graph[parent].push_back(child);
          }
          if (child == endWord)
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      currentLevelWords = move(nextLevelWords);
    }

    return true;
  }

  void getChildren(const string& parent, const unordered_set<string>& wordSet,
                   vector<string>& children) {
    string s(parent);

    for (int i = 0; i < s.length(); ++i) {
      const char cache = s[i];
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        s[i] = c;  // now is `child`
        if (wordSet.count(s))
          children.push_back(s);
      }
      s[i] = cache;
    }
  }

  void dfs(const unordered_map<string, vector<string>>& graph,
           const string& word, const string& endWord, vector<string>&& path,
           vector<vector<string>>& ans) {
    if (word == endWord) {
      ans.push_back(path);
      return;
    }
    if (!graph.count(word))
      return;

    for (const string& child : graph.at(word)) {
      path.push_back(child);
      dfs(graph, child, endWord, move(path), ans);
      path.pop_back();
    }
  }
};

class Solution {
  public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Set<String> wordSet = new HashSet<>(wordList);
    if (!wordSet.contains(endWord))
      return new ArrayList<>();

    // {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    Map<String, List<String>> graph = new HashMap<>();

    // build graph from beginWord -> endWord
    if (!bfs(beginWord, endWord, wordSet, graph))
      return new ArrayList<>();

    List<List<String>> ans = new ArrayList<>();
    List<String> path = new ArrayList<>(Arrays.asList(beginWord));

    dfs(graph, beginWord, endWord, path, ans);
    return ans;
  }

  private boolean bfs(final String beginWord, final String endWord, Set<String> wordSet,
                      Map<String, List<String>> graph) {
    Set<String> currentLevelWords = new HashSet<>();
    currentLevelWords.add(beginWord);
    boolean reachEndWord = false;

    while (!currentLevelWords.isEmpty()) {
      for (final String word : currentLevelWords)
        wordSet.remove(word);
      Set<String> nextLevelWords = new HashSet<>();
      for (final String parent : currentLevelWords) {
        graph.putIfAbsent(parent, new ArrayList<>());
        for (final String child : getChildren(parent, wordSet)) {
          if (wordSet.contains(child)) {
            nextLevelWords.add(child);
            graph.get(parent).add(child);
          }
          if (child.equals(endWord))
            reachEndWord = true;
        }
      }
      if (reachEndWord)
        return true;
      currentLevelWords = nextLevelWords;
    }

    return false;
  }

  private List<String> getChildren(final String parent, Set<String> wordSet) {
    List<String> children = new ArrayList<>();
    StringBuilder sb = new StringBuilder(parent);

    for (int i = 0; i < sb.length(); ++i) {
      final char cache = sb.charAt(i);
      for (char c = 'a'; c <= 'z'; ++c) {
        if (c == cache)
          continue;
        sb.setCharAt(i, c);
        final String child = sb.toString();
        if (wordSet.contains(child))
          children.add(child);
      }
      sb.setCharAt(i, cache);
    }

    return children;
  }

  private void dfs(Map<String, List<String>> graph, final String word, final String endWord,
                   List<String> path, List<List<String>> ans) {
    if (word.equals(endWord)) {
      ans.add(new ArrayList<>(path));
      return;
    }
    if (!graph.containsKey(word))
      return;

    for (final String child : graph.get(word)) {
      path.add(child);
      dfs(graph, child, endWord, path, ans);
      path.remove(path.size() - 1);
    }
  }
}

class Solution:
  def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    wordSet = set(wordList)
    if endWord not in wordList:
      return []

    # {"hit": ["hot"], "hot": ["dot", "lot"], ...}
    graph: Dict[str, List[str]] = defaultdict(list)

    # build graph from beginWord -> endWord
    if not self._bfs(beginWord, endWord, wordSet, graph):
      return []

    ans = []

    self._dfs(graph, beginWord, endWord, [beginWord], ans)
    return ans

  def _bfs(self, beginWord: str, endWord: str, wordSet: Set[str], graph: Dict[str, List[str]]) -> bool:
    currentLevelWords = {beginWord}

    while currentLevelWords:
      for word in currentLevelWords:
        wordSet.discard(word)
      nextLevelWords = set()
      reachEndWord = False
      for parent in currentLevelWords:
        for child in self._getChildren(parent, wordSet):
          if child in wordSet:
            nextLevelWords.add(child)
            graph[parent].append(child)
          if child == endWord:
            reachEndWord = True
      if reachEndWord:
        return True
      currentLevelWords = nextLevelWords

    return False

  def _getChildren(self, parent: str, wordSet: Set[str]) -> List[str]:
    children = []
    s = list(parent)

    for i, cache in enumerate(s):
      for c in string.ascii_lowercase:
        if c == cache:
          continue
        s[i] = c
        child = ''.join(s)
        if child in wordSet:
          children.append(child)
      s[i] = cache

    return children

  def _dfs(self, graph: Dict[str, List[str]], word: str, endWord: str, path: List[str], ans: List[List[str]]) -> None:
    if word == endWord:
      ans.append(path.copy())
      return

    for child in graph.get(word, []):
      path.append(child)
      self._dfs(graph, child, endWord, path, ans)
      path.pop()

class Solution {
 public:
  vector<vector<string>> findLadders(string beginWord, string endWord,
                                     vector<string>& wordList) {
    vector<vector<string>> ans;
    unordered_set<string> wordSet(begin(wordList), end(wordList));
    queue<vector<string>> paths{{{beginWord}}};  // {{"hit"}}

    while (!paths.empty()) {
      unordered_set<string> currentLevelVisited;
      for (int sz = paths.size(); sz > 0; --sz) {
        vector<string> path = paths.front();
        paths.pop();                    // {"hit"}
        string lastWord = path.back();  // "hit"
        for (int i = 0; i < lastWord.length(); ++i) {
          char cache = lastWord[i];  // cache = 'i'
          for (char c = 'a'; c <= 'z'; ++c) {
            lastWord[i] = c;                // "hit" -> "hot" (temporarily)
            if (wordSet.count(lastWord)) {  // find "hot" in wordSet
              currentLevelVisited.insert(lastWord);  // mark "hot" as visited
              vector<string> nextPath(path);
              nextPath.push_back(lastWord);  // nextPath = {"hit", "hot"}
              if (lastWord == endWord)
                ans.push_back(nextPath);
              else
                paths.push(nextPath);
            }
          }
          lastWord[i] = cache;  // "hot" back to "hit"
        }
      }
      for (const string& word : currentLevelVisited)
        wordSet.erase(word);
    }

    return ans;
  }
};