Word Ladder II - Trie sem wildcard

struct TrieNode {
  vector<int> end_words;
  unordered_map<char, unique_ptr<TrieNode>> children;
};

class Trie {
public:
  void insert(const string& word, int word_index) {
    TrieNode* curr;
    curr = &head;

    for (const char c : word) {
      TrieNode* next;
      auto it = curr->children.find(c);
      if (it != curr->children.end()) {
        next = it->second.get();
      } else {
        next = new TrieNode();
        curr->children[c] = unique_ptr<TrieNode>(next);
      }
      curr = next;
    }
    curr->end_words.push_back(word_index);
  }

  vector<int> findOneDiffs(const string& word, int word_index) {
    vector<pair<TrieNode*, bool>> curr;
    curr.push_back(make_pair(&head, false));

    for (const char c : word) {
      vector<pair<TrieNode*, bool>> next_curr;
      for (const auto& p : curr) {
        TrieNode* node = p.first;
        bool used_wildcard = p.second;
        if (!used_wildcard) {
          for (auto& child : node->children) {
            next_curr.push_back(make_pair(child.second.get(), true));
          }
        }
        auto it = node->children.find(c);
        if (it != node->children.end()) {
          next_curr.push_back(make_pair(it->second.get(), used_wildcard));
        }
      }
      swap(curr, next_curr);
    }

    vector<int> result;
    for (const auto& p : curr) {
      TrieNode* node = p.first;
      for (const int i : node->end_words) {
        if (i != word_index) {
          result.push_back(i);
        }
      }
    }
    return result;
  }

private:
  TrieNode head;
};

class Solution {
public:

  vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
    wordList.push_back(beginWord);
    vector<vector<int>> transform (wordList.size());

    int target = -1;
    for (int i = 0; i < wordList.size() - 1; i++) {
      if (endWord == wordList[i]) {
        target = i;
        break;
      }
    }
    if (target == -1) {
      return vector<vector<string>>();
    }

    Trie trie;
    for (int i = 0; i < wordList.size(); i++) {
      trie.insert(wordList[i], i);
    }

    for (int i = 0; i < wordList.size(); i++) {
      vector<int> one_diffs = trie.findOneDiffs(wordList[i], i);
      for (const int j : one_diffs) {
        transform[i].push_back(j);
      }
    }

    vector<vector<vector<string>>> ways_to_get(wordList.size());
    deque<int> next;
    vector<int> distance(wordList.size(), -1);

    next.push_back(wordList.size() - 1);
    distance[wordList.size() - 1] = 0;
    ways_to_get[wordList.size() - 1].push_back({wordList[wordList.size() - 1]});

    while (!next.empty()) {
      int curr = next.front();
      next.pop_front();
      if (curr == target) {
        break;
      }

      for (const int i : transform[curr]) {
        if (distance[i] == -1) {
          distance[i] = distance[curr] + 1;
          next.push_back(i);
        }
        if (distance[i] == distance[curr] + 1) {
          for (vector<string> v : ways_to_get[curr]) {
            v.push_back(wordList[i]);
            ways_to_get[i].push_back(v);
          }
        }
      }
    }
    return ways_to_get[target];
  }
};