139. Word Break

[!info] https://leetcode.com/problems/word-break/description/

#include <iostream>
#include <optional>
#include <print>
#include <unordered_map>
#include <vector>

class Trie {
private:
    class TrieNode {
    public:
        bool isWord = false;
        std::unordered_map<char, TrieNode*> children = {};
    };

    TrieNode* root = new TrieNode();

public:
    void addWord(std::string_view const& str) {
        if (str.empty()) {
            return;
        }

        auto curNode = root;
        for (auto const& c: str) {
            auto& nextNode = curNode->children[c];
            if (!nextNode) {
                nextNode = new TrieNode();
            }
            curNode = nextNode;
        }
        curNode->isWord = true;
    }

    template<typename Callback>
    bool matchPrefixLengths(std::string_view const& str, Callback&& callback) const {
        auto curNode = root;
        int prefixLength = 0;

        for (auto const& c: str) {
            ++prefixLength;
            curNode = curNode->children[c];
            if (!curNode) {
                return false;
            }
            if (curNode->isWord) {
                if (callback(prefixLength)) {
                    return true;
                }
            }
        }

        return false;
    }
};

bool wordBreak(std::string_view const& str, std::vector<std::string> const& wordDict) {
    auto trie = Trie();
    for (auto const& word: wordDict) {
        trie.addWord(word);
    }

    auto isWordBreakPossibleDp = std::unordered_map<std::string_view, std::optional<bool>> {};

    auto isWordBreakPossible = [&](this auto&& isWordBreakPossible, std::string_view const& str) -> bool {
        std::println("isWordBreakPossible called | str: {}", str);

        auto& dpVal = isWordBreakPossibleDp[str];
        if (dpVal) {
            return *dpVal;
        }

        if (str.empty()) {
            dpVal = true;
            return *dpVal;
        }

        dpVal = trie.matchPrefixLengths(str, [&](auto const& matchedPrefixLength) -> bool {
            auto remainingStr = std::string_view { str.begin() + matchedPrefixLength, str.end() };
            return isWordBreakPossible(remainingStr);
        });

        return *dpVal;
    };

    return isWordBreakPossible(str);
}

int main() {
    using namespace std::literals;
    auto words = std::vector<std::string> {"cat", "sand", "sands", "cats", "an", "and", "do", "dog"};
    std::println("answer: {}", wordBreak("catsanddogs"s, words));
}