使用辅助函数为尝试和链表等数据结构构建节点的目的是什么？

Question

我一直在研究Leetcode问题，试图提高我的编码技能，在做这个问题时我对此感到好奇https://leetcode.com/problems/implement-trie-prefix-tree/

我在网上找到的大多数答案都是通过创建节点结构，然后使用构建方法来实例化节点并用默认值填充它来实现 trie。但我想知道为什么这是必要的，并且他们不只是用这些默认值定义节点？ 我尝试过，它似乎在没有构建方法的情况下工作得完全相同，所以我必须假设这是某种最佳实践的原因。我可以理解为什么构建方法对于更复杂的节点结构会更好。但是，我真正感兴趣的是我所做的事情可能会出什么问题，因为我无法找到任何结论性的答案。

典型解决方案：

class Trie {

private:

    struct Node {
        bool isWord = false;
        Node* children[26];
    };


    Node* buildNode(){// helper method to build the default node
        Node* root = new Node();
        root-> isWord = false;
        for (int i = 0; i<26; i++){
            root->children[i] = NULL;
        }
        return root;
    }

    Node* root;

public:
    Trie() {
        root = buildNode();
    }
    
    void insert(string word) {
        Node* curr = root;
        for (char ch : word){
            int index = ch - 'a'; // convert char to int 0-25
            if (!curr->children[index]){//if NULL
                curr->children[index] = buildNode();
            }
            curr = curr->children[index];
        }
        curr->isWord = true;
    }

我的解决方案：

class Trie {

private:

    struct Node {
        bool isWord = false;
        Node* children[26] = {};
    };

    Node* root;

public:
    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        Node* curr = root;
        for (char ch : word){
            int index = ch - 'a'; // convert char to int 0-25
            if (!curr->children[index]){//if NULL
                curr->children[index] = new Node();
            }
            curr = curr->children[index];
        }
        curr->isWord = true;
    }

两种实现似乎都以相同的方式工作和执行。那么为什么第一个比第二个更受欢迎？

Answer 1

LeetCode 有问题

正如评论中所指出的，您的代码可以完成工作。我希望它能通过所有 LeetCode 测试。

但是肯定没有通过我的！尽管我比具有单独“构建”例程的解决方案更喜欢您的解决方案，但如果您将代码提交给求职面试官，您可能会遇到麻烦。不幸的是，整个事情是一个巨大的内存泄漏。如果您想使用运算符

new

和原始指针，您有责任编写一个适当的析构函数来在完成后进行清理。

LeetCode 允许你跳过这一点这一事实让人们说：

...因为 leetcode 不教授 C++ 和良好的 C++ 实践。

大多数 leetcode 解决方案（不幸的是包括你的）永远不会在一个像样的工程环境中投入生产。

学习语言时避免竞争性编码网站。许多（大多数）提倡可怕的基本编码实践......

即使你提供了析构函数，我认为你的解决方案仍然应该被 LeetCode 拒绝，因为它没有使用标准库中的智能指针之一。在生产环境中，类

Trie

几乎肯定会使用

std::unique_ptr

进行编码。

使用标准库中的工具

当我解决这个问题时，我通过使用

std::unique_ptr

和

std::array

回避了整个清理问题。我不仅避免了编写析构函数的任务，而且还完全不需要编写任何类型的“构建”代码。我回避了一大堆容易出错的单调乏味的事情！

我的代码遵循维基百科上的示例，因此它使用名称

is_terminal

而不是

isWord

。除此之外，我们的

insert

例程基本相同。

我的添加了对有效字符的检查，但这可能是一个缺陷，因为规范承诺

word

中的所有字符都是小写字母。我的双重检查只会减慢速度。如果我能够满意地证明

Trie

类的所有客户都遵守先决条件，我将删除额外的检查。

class Trie
{
    // This implementation anticipates that the letters 'a' to 'z' 
    // have consectutive code points in the character set used 
    // by std::string. 
    // 
    // When such is not true, it will still work, albeit, with a 
    // lot of wasted storage, so long as 'a' precedes all other 
    // lower-case letters, and `z` comes after all others.
    struct Node
    {
        enum : std::size_t { alphabet_size = 'z' - 'a' + 1u };
        std::array<std::unique_ptr<Node>, alphabet_size> child;
        bool is_terminal{ false };
    };
    std::unique_ptr<Node> root;
public:
    Trie()
        : root{ std::make_unique<Node>() }
    {}
    void insert(std::string word)
    {
        Node* p{ root.get() };
        for (auto const& ch : word)
        {
            auto const i{ to_subscript(ch) };
            if (!p->child[i])
                p->child[i] = std::make_unique<Node>();
            p = p->child[i].get();
        }
        p->is_terminal = true;
    }
    bool search(std::string word)
    {
        Node* p{ root.get() };
        for (auto const& ch : word)
        {
            auto const i{ to_subscript(ch) };
            if (!p->child[i])
                return false;
            p = p->child[i].get();
        }
        return p->is_terminal;
    }
    bool startsWith(std::string prefix)
    {
        Node* p{ root.get() };
        for (auto const& ch : prefix)
        {
            auto const i{ to_subscript(ch) };
            if (!p->child[i])
                return false;
            p = p->child[i].get();
        }
        return true;
    }
private:
    auto static to_subscript(char const ch)
    {
        auto const i{ std::tolower(static_cast<unsigned char>(ch)) };
        if (!std::isalpha(i))
            throw std::runtime_error(std::format(
                "ERROR: Trie character is not alphabetic: '{}'", ch));
        return static_cast<std::size_t>(i - 'a');
    }
};