1 Тема від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 583
    • Репутація: 126

Тема: Створення Trie з використанням unordered_map

Знову завдання з LeetCode.
Намагаюся створити префіксне дерево за допомогою unordered_map, ось так:
main.cpp

#include "MyTrie.h"
#include <iostream>

using namespace std;

int main()
{
    Trie* obj = new Trie();
    obj->insert("striver");
    delete obj;
    return 0;
}

MyTrie.h

#include <memory>
#include <string>
#include <unordered_map>

using namespace std;

struct TrieNode {

    unordered_map<char, shared_ptr<TrieNode>> childNode;

    bool wordEnd;

    TrieNode()
    {
        wordEnd = false;
    }
};

class Trie {
private:
    shared_ptr<TrieNode> root;

public:
    Trie()
    {
    }

    void insert(string word)
    {
        shared_ptr<TrieNode> node = root;
        for (auto& letter : word) {
            if (node->childNode.count(letter) == 0) {
                shared_ptr<TrieNode> new_node;
                node->childNode.emplace(letter, new_node);
            }
            node = node->childNode.at(letter);
        }
        node->wordEnd = true;
    }
};

Але з'являється помилка:

[ 50%] Building CXX object CMakeFiles/trie.dir/main.cpp.o
[100%] Linking CXX executable trie
make[2]: *** [CMakeFiles/trie.dir/build.make:98: trie] Помилка адресування (зроблений дамп пам'яті)
make[2]: *** Вилучаємо файл "trie"
make[1]: *** [CMakeFiles/Makefile2:83: CMakeFiles/trie.dir/all] Помилка 2
make: *** [Makefile:136: all] Помилка 2

Розумію, що десь неправильно звертаюся до пам'яті, але не розумію, де саме.

2 Відповідь від Teg Miles

  • Teg Miles
  • Teg Miles
  • Користувач
  • Поза форумом
  • Дата реєстрації: 20.01.2016
  • Повідомлень: 583
    • Репутація: 126

Re: Створення Trie з використанням unordered_map

Знову неправильно використав розумні вказівники.
Ось рішення,  яке прийняв LeetCode:

struct TrieNode {

    unordered_map<char, shared_ptr<TrieNode>> childNode;

    bool wordEnd;

    TrieNode()
    {
        wordEnd = false;
    }
};

class Trie {
private:
    shared_ptr<TrieNode> root = make_shared<TrieNode>();

public:
    Trie()
    {
    }

    void insert(string word)
    {

        auto* node = root.get();

        for (auto& letter : word) {
            if (!node->childNode.contains(letter)) {

                node->childNode.emplace(letter, make_shared<TrieNode>());
            }
            node = node->childNode.at(letter).get();
        }
        node->wordEnd = true;
    }

    bool search(string word)
    {
        auto* node = root.get();
        for (auto& letter : word) {
            if (node->childNode.count(letter) == 0) {
                return false;
            }
            node = node->childNode.at(letter).get();
        }
        return node->wordEnd;
    }

    bool startsWith(string prefix)
    {
        auto* node = root.get();
        for (auto& letter : prefix) {
            if (node->childNode.count(letter) == 0) {
                return false;
            }
            node = node->childNode.at(letter).get();
        }
        return true;
    }
};