LeetCode 1032:字符流

Question

我在这里发布了一个LeetCode问题的代码。如果您有时间和想复习，请这样做。谢谢!

问题实现StreamChecker类如下所示：

• StreamChecker(words)：构造函数，用给定的单词插入数据结构。
• query(letter)：返回真当且仅当对于某些k >= 1，查询的最后k个字符(从最老到最新，包括刚才查询的这封信)拼写给定列表中的一个单词。

示例: StreamChecker streamChecker = new (“cd”、“f”、“kl”)；// init字典。streamChecker.query('a')；//返回false streamChecker.query('b')；//返回false streamChecker.query('c')；//返回false streamChecker.query('d')；//返回true，因为'cd‘在单词列表streamChecker.query(’e‘)中；//返回false streamChecker.query('f')；//返回真，因为'f‘在单词列表streamChecker.query(’g‘)中；//返回false streamChecker.query('h')；//返回false streamChecker.query('i')；//返回false streamChecker.query('j')；//返回false streamChecker.query('k')；//返回false streamChecker.query('l')；//返回true，因为'kl‘在单词列表注释中：

1 \le \text{words.length} \le 2000

1 \le \text{words[i].length} \le 2000

• 单词将只由小写英文字母组成。
• 查询将只包含小写英文字母。
• 查询的数量最多为40000次。

码

#include <unordered_map>
#include <string>
#include <algorithm>

class Trie {
    std::unordered_map<char, Trie*> alphabet_map;
    bool is_word;

public:
    Trie() {
        is_word = false;
    }

    // Inserts in the trie
    void insert(const std::string word) {
        if (word.length() == 0) {
            return;
        }

        Trie* temp_trie = this;

        for (auto letter : word) {
            if (temp_trie->alphabet_map.find(letter) != temp_trie->alphabet_map.end()) {
                temp_trie = temp_trie->alphabet_map[letter];

            } else {
                temp_trie->alphabet_map[letter] = new Trie();
                temp_trie = temp_trie->alphabet_map[letter];
            }
        }

        temp_trie->is_word = true;
    }

    // Searches the word in the trie
    bool search(const std::string word) {
        if (word.length() == 0) {
            return false;
        }

        Trie* temp_trie = this;

        for (auto letter : word) {
            if (temp_trie->alphabet_map.find(letter) == temp_trie->alphabet_map.end()) {
                return false;
            }

            temp_trie = temp_trie->alphabet_map[letter];

            if (temp_trie->is_word) {
                return true;
            }
        }

        return temp_trie->is_word;
    }
};

class StreamChecker {
    Trie trie_stream;
    std::string string_stream = "";
    int word_length = 0;

public:
    StreamChecker(const std::vector<std::string>& words) {
        for (auto word : words) {
            std::reverse(word.begin(), word.end());
            word_length = std::max(word_length, (int) word.length());
            trie_stream.insert(word);
        }
    }


    bool query(const char letter) {
        string_stream = letter + string_stream;

        if (string_stream.length() > word_length) {
            string_stream.pop_back();
        }

        return trie_stream.search(string_stream);
    }
};

参考

LeetCode有一个回答问题的模板。通常有一个名为Solution的类，它有一个或多个public函数，我们不允许重命名这些函数。对于这个问题，模板是：

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        
    }
    
    bool query(char letter) {
        
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

• 问题
• 讨论
• 特瑞

Answer 1

模板

您不能重命名函数，但您可以更改它们的签名吗？即

StreamChecker(vector<string>& words) {

会更好

StreamChecker(const vector<string> &words) {

类似地，

void insert(const std::string word) {

应该是

void insert(const std::string &word) {

search也是如此。

另外，const在

bool query(const char letter) {

并不是那么重要，因为letter本身就是一个不变的字母。如果这是一个引用或指针，那就更重要了。

最后，search方法不修改成员，因此：

bool search(const std::string &word) const {

Answer 2

除了莱因德林所说的：

Move class Trie inside class StreamChecker

您的class Trie不是泛型类，而是专门针对StreamChecker的trie实现。您可以将它移动到class StreamChecker中，这样就可以清楚地知道它们是属于彼此的，这样class Trie就不会污染全局命名空间：

class StreamChecker {
    class Trie {
        ...
    };

    Trie trie_stream;
    ...
};

Tries按价值

您的class Trie有一个内存泄漏:它调用new Trie()，但是看不到相应的delete。您可以编写一个在alphabet_map上迭代并对值调用delete的析构函数，甚至可以使用std::unique_ptr来跟踪内存的所有权，但是根本不需要这样做。毕竟，std::map已经负责管理存储键和值所需的内存。因此，移除该指针并写入：

class Trie {
    std::unordered_map<char, Trie> alphabet_map;
    ...
    void insert(const std::string &word) {
        if (word.empty()) {
            return;
        }

        Trie *temp_trie = this;

        for (auto letter: word) {
             temp_trie = &temp_trie->alphabet_map[letter];
        }

        temp_trie->is_word = true;
    }
};

注意，在search()中，您需要进行类似的修改，但是在这里您确实需要显式地检查letter是否存在于alphabet_map中。