<p>A <strong>transformation sequence</strong> from word <code>beginWord</code> to word <code>endWord</code> using a dictionary <code>wordList</code> is a sequence of words <code>beginWord -&gt; s<sub>1</sub> -&gt; s<sub>2</sub> -&gt; ... -&gt; s<sub>k</sub></code> such that:</p>

<ul>
	<li>Every adjacent pair of words differs by a single letter.</li>
	<li>Every <code>s<sub>i</sub></code> for <code>1 &lt;= i &lt;= k</code> is in <code>wordList</code>. Note that <code>beginWord</code> does not need to be in <code>wordList</code>.</li>
	<li><code>s<sub>k</sub> == endWord</code></li>
</ul>

<p>Given two words, <code>beginWord</code> and <code>endWord</code>, and a dictionary <code>wordList</code>, return <em>all the <strong>shortest transformation sequences</strong> from</em> <code>beginWord</code> <em>to</em> <code>endWord</code><em>, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words </em><code>[beginWord, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub>]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]
<strong>Output:</strong> [[&quot;hit&quot;,&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;cog&quot;],[&quot;hit&quot;,&quot;hot&quot;,&quot;lot&quot;,&quot;log&quot;,&quot;cog&quot;]]
<strong>Explanation:</strong>&nbsp;There are 2 shortest transformation sequences:
&quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;dot&quot; -&gt; &quot;dog&quot; -&gt; &quot;cog&quot;
&quot;hit&quot; -&gt; &quot;hot&quot; -&gt; &quot;lot&quot; -&gt; &quot;log&quot; -&gt; &quot;cog&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> beginWord = &quot;hit&quot;, endWord = &quot;cog&quot;, wordList = [&quot;hot&quot;,&quot;dot&quot;,&quot;dog&quot;,&quot;lot&quot;,&quot;log&quot;]
<strong>Output:</strong> []
<strong>Explanation:</strong> The endWord &quot;cog&quot; is not in wordList, therefore there is no valid transformation sequence.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= beginWord.length &lt;= 5</code></li>
	<li><code>endWord.length == beginWord.length</code></li>
	<li><code>1 &lt;= wordList.length &lt;= 500</code></li>
	<li><code>wordList[i].length == beginWord.length</code></li>
	<li><code>beginWord</code>, <code>endWord</code>, and <code>wordList[i]</code> consist of lowercase English letters.</li>
	<li><code>beginWord != endWord</code></li>
	<li>All the words in <code>wordList</code> are <strong>unique</strong>.</li>
	<li>The <strong>sum</strong> of all shortest transformation sequences does not exceed <code>10<sup>5</sup></code>.</li>
</ul>

class Solution {
public:
    class Trie {
        std::optional<std::array<Trie*, 26>> m_children = std::nullopt;
    public:
        Trie() = default;
        ~Trie() {
            if (m_children) {
                for (auto& c : *m_children) {
                    delete c;
                }
            }
        }

        [[nodiscard]] bool isLeaf() const { return !m_children.has_value(); }

        void insert(std::string_view str) {
            if (!str.empty()) {
                auto i = str.front() - 'a';

                if (!m_children) {
                    m_children.emplace();
                    for (auto& v : *m_children) { v = nullptr; }
                }

                if (m_children->at(i) == nullptr) {
                    m_children->at(i) = new Trie();
                }

                m_children->at(i)->insert(str.substr(1));
            }
        }

        [[nodiscard]]
        std::vector<std::string> find_differing_by_1(std::string_view str) const {
            std::vector<std::string> out;

            _query_differing(str, 0, out);

            return out;
        }

        void _query_differing(
            // This is the entire string.
            std::string_view str,
            // This is the length of the substring we've matched up until this point.
            std::size_t depth,
            // This is the collection of words we've found.
            std::vector<std::string>& acc
        ) const {
            std::string_view prefix = str.substr(0, depth);

            if (depth == str.size()) {
                // We've reached the last character, no more children to traverse.
                assert(isLeaf() == true);
                return;
            } else {
                assert(isLeaf() == false);

                // This is the next character in the target string that we need to search...
                auto ii = str.at(depth) - 'a';

                // Otherwise, we'll need to actually look through our children...
                std::string_view suffix = str.substr(depth + 1); // skip the next character.

                std::string tmp{str}; // This is the string that we will mutate.

                for (std::size_t i = 0; i < 26; ++i) {
                    if (m_children->at(i)) {
                        if (i == ii) {
                            // We've matched at str[depth], let's find strings that differ by 1 in the remainder of the
                            // string.
                            m_children->at(i)->_query_differing(str, depth + 1, acc);
                        } else {
                            // Otherwise, this node is a mismatch - and if it contains the suffix in its children, then
                            // the string will only differ by 1.
                            if (m_children->at(i)->contains(suffix)) {
                                char c = 'a' + i;
                                tmp[depth] = c;
                                acc.push_back(tmp);
                            }
                        }
                    }
                }
            }
        }

        bool contains(std::string_view str) const {
            if (str.empty()) {
                // We should make our way down to the leaf nodes (singe they're all of the same height)
                assert(isLeaf() == true);
                return true;
            } else {
                auto i = str.front() - 'a';
                assert(isLeaf() == false);

                if (m_children->at(i) == nullptr) {
                    return false;
                } else {
                    return m_children->at(i)->contains(str.substr(1));
                }
            }
        }
    };

    int ladderLength(
        const std::string& beginWord,
        const std::string& endWord,
        const std::vector<std::string>& wordList
    ) {
        Trie trie{};

        for (const auto& word : wordList) {
            trie.insert(std::string_view{word});
        }

        if (!trie.contains(std::string_view{endWord})) {
            return 0; // Edge case, impossible to reach the end...
        }

        std::queue<std::pair<std::string, int>> queue;

        queue.emplace(beginWord, 1);

        std::unordered_set<std::string> seen;
        std::unordered_set<std::string> willExpand;

        willExpand.emplace(beginWord);

        while (!queue.empty()) {
            auto [str, cost] = queue.front();
            queue.pop();

            if (str == endWord) {
                return cost;
            }

            if (seen.emplace(str).second) {
                // First time seeing this node, let's explore its children.
                auto children = trie.find_differing_by_1(str);

                for (const auto& child : children) {
                    if (willExpand.emplace(child).second) {
                        queue.emplace(child, cost + 1);
                    }
                }
            }
        }

        return 0; // Not possible...
    }

    struct Record {
        std::string str;
        std::size_t min_distance = std::numeric_limits<std::size_t>::max();
        std::vector<std::size_t> parents{};
    };

    void expand_paths(
        const std::vector<Record>& graph,
        std::size_t               current_node,
        std::vector<std::string>& current_path,
        std::vector<std::vector<std::string>>& paths
    ) {
        if (current_node == 0) {
            if (!paths.empty()) {
                assert(paths.front().size() == current_path.size() + 1);
            }

            paths.emplace_back();
            paths.back().push_back(graph[current_node].str);

            for (auto it = current_path.rbegin(); it != current_path.rend(); ++it) {
                paths.back().push_back(*it);
            }
            return;
        }

        for (const auto& parent : graph[current_node].parents) {
            current_path.push_back(graph[current_node].str);

            // Recursive call for its parent
            expand_paths(
                graph,
                parent,
                current_path,
                paths
            );

            current_path.pop_back();
        }
    }

    std::vector<std::vector<std::string>> findLadders(
        const std::string& beginWord,
        const std::string& endWord,
        const std::vector<std::string>& wordList
    ) {
        Trie trie{};

        for (const auto& word : wordList) {
            trie.insert(std::string_view{word});
        }

        if (!trie.contains(std::string_view{endWord})) {
            return {}; // Edge case, impossible to reach the end...
        }

        std::unordered_map<std::string, std::size_t> strToIdx;

        std::vector<Record> nodes;
        nodes.reserve(wordList.size() + 1);

        auto addWord = [&](const auto& str) {
            auto id = nodes.size();

            nodes.push_back(
                Record{
                    str,
                    std::numeric_limits<std::size_t>::max(),
                    std::vector<std::size_t>{}
                }
            );

            strToIdx.insert(std::make_pair(str, id));
        };

        addWord(beginWord);
        for (const auto& word : wordList) { addWord(word); }

        std::queue<std::size_t> queue;

        queue.push(0);
        nodes[0].min_distance = 1;

        while (!queue.empty()) {
            auto node_id = queue.front();
            queue.pop();

            const auto& node = nodes[node_id];

            for (const auto& child_str : trie.find_differing_by_1(node.str)) {
                auto& child_id = strToIdx[child_str];
                auto& child = nodes[child_id];

                if (child.min_distance > node.min_distance + 1) {
                    // A shorted distance to our child has been found,
                    child.min_distance = node.min_distance + 1;
                    child.parents.clear();
                    child.parents.push_back(node_id);

                    queue.push(child_id);
                }
                else if (child.min_distance == node.min_distance + 1) {
                    // We've found another equivalent distance.
                    child.parents.push_back(node_id);
                }
            }
        }

        std::vector<std::vector<std::string>> out;
        std::vector<std::string>              acc;

        expand_paths(
            nodes,
            strToIdx[endWord],
            acc,
            out
        );

        return out;
    }
};

20000