[C++] Object Oriented Programming

https://leetcode.com/problems/implement-trie-prefix-tree/description/

 

Trie.h

#pragma once
#include <string>


class TrieNode
{
private:
	char ch;
	bool isWord;
	TrieNode* children[26] {nullptr};

public:
	TrieNode(char ch, bool isWord=false);
	TrieNode(const TrieNode& node);
	TrieNode(TrieNode&& node);
	TrieNode& operator=(const TrieNode& rhs);
	TrieNode& operator=(TrieNode&& rhs);
	
	char getCh() const;
	bool getIsWord() const;
	void setIsWord(bool isWord);
	TrieNode* getChild(int idx) const;
	void setChild(int idx, TrieNode* node);
	
	~TrieNode();
};


class Trie 
{
private:
	TrieNode* root;
	
public:
	Trie();
	Trie(const Trie& trie);
	Trie(Trie&& trie);
	Trie& operator=(const Trie& rhs);
	Trie& operator=(Trie&& rhs);
	
	TrieNode* getRoot() const;
	void setRoot(TrieNode* node);
	void insert(std::string word);
	bool search(std::string word);
	bool startsWith(std::string prefix);
	
	~Trie();
	
	friend void displayTrie(Trie& trie);
};


void displayTrie(Trie& trie);

 

Trie.cpp

#include <string>
#include <vector>
#include <iostream>

#include "Trie.h"


TrieNode::TrieNode(char ch, bool isWord) : ch(ch), isWord(isWord) {}

TrieNode::TrieNode(const TrieNode& node) : ch(node.getCh()), isWord(node.getIsWord()) {
	for (int i = 0; i < 26; i++) {
		if (node.getChild(i) != nullptr) {
			children[i] = new TrieNode(*(node.getChild(i)));
		}	
		else {
			children[i] = nullptr;
		}
	}
}

TrieNode::TrieNode(TrieNode&& node) : ch(node.getCh()), isWord(node.getIsWord()) {
	for (int i = 0; i < 26; i++) {
		children[i] = node.getChild(i);
        node.setChild(i, nullptr);
	}
}

TrieNode& TrieNode::operator=(const TrieNode& rhs) {
	if(this == &rhs) return *this;
	this->ch = rhs.getCh();
	this->isWord = rhs.getIsWord();
	for (int i = 0; i < 26; i++) {
		if(rhs.getChild(i) != nullptr) {
			children[i] = new TrieNode(*rhs.getChild(i));
		} else {
			children[i] = nullptr;
		}
	}
	return *this;
}

TrieNode& TrieNode::operator=(TrieNode&& rhs) {
	if(this == &rhs) return *this;
	this->ch = rhs.getCh();
	this->isWord = rhs.getIsWord();
	for (int i = 0; i < 26; i++) {
		children[i] = rhs.getChild(i);
        rhs.setChild(i, nullptr);
	}
	return *this;
}

char TrieNode::getCh() const {
	return ch;
}

bool TrieNode::getIsWord() const {
	return isWord;
}

void TrieNode::setIsWord(bool isWord) {
	this->isWord = isWord;
}

TrieNode* TrieNode::getChild(int idx) const {
	return children[idx];
}

void TrieNode::setChild(int idx, TrieNode* node) {
	children[idx] = node;
}

TrieNode::~TrieNode() {
	for (int i = 0; i < 26; i++) {
		if (children[i] != nullptr) {
			delete children[i];
		}
	}
}

Trie::Trie() {
	root = new TrieNode('R');
}

Trie::Trie(const Trie& trie) {
	root = new TrieNode(*trie.getRoot());
}

Trie::Trie(Trie&& trie) {
	root = trie.getRoot();
	trie.setRoot(nullptr);
}

Trie& Trie::operator=(const Trie& rhs) {
	if (this == &rhs) return *this;
	root = new TrieNode(*rhs.getRoot());
	return *this;
}

Trie& Trie::operator=(Trie&& rhs) {
	if (this == &rhs) return *this;
	root = rhs.getRoot();
	rhs.setRoot(nullptr);
	return *this;
}

TrieNode* Trie::getRoot() const {
	return root;
}

void Trie::setRoot(TrieNode* node) {
	root = node;
}

void Trie::insert(std::string word) {
	TrieNode* cur = getRoot();
	for (char c : word) {
		int idx = c - 'a';
		if (cur->getChild(idx) == nullptr) {
			TrieNode* node = new TrieNode(c);
			cur->setChild(idx, node);
		}
		cur = cur->getChild(idx);
	}
	cur->setIsWord(true);
}

bool Trie::search(std::string word) {
	TrieNode* cur = getRoot();
	for (char c : word) {
		int idx = c - 'a';
		if (cur->getChild(idx) == nullptr) {
			return false;
		}
		cur = cur->getChild(idx);
	}
	return cur->getIsWord();
}

bool Trie::startsWith(std::string prefix) {
	TrieNode* cur = getRoot();
	for (char c : prefix) {
		int idx = c - 'a';
		if (cur->getChild(idx) == nullptr) {
			return false;
		}
		cur = cur->getChild(idx);
	}
	return true;
}

Trie::~Trie() {
	if (root != nullptr) delete root;
}

void displayTrieHelper(std::vector<std::string>& words, TrieNode& node, std::string word) {
	std::string cur = word + node.getCh();
	if (node.getIsWord() == true) {
		words.push_back(cur);
	}
	for (int i = 0; i < 26; i++) {
		TrieNode* child = node.getChild(i);
		if (child != nullptr) {
			displayTrieHelper(words, *child, cur);
		}
	}
}

void displayTrie(Trie& trie) {
	std::vector<std::string> words;
	TrieNode* root = trie.getRoot();
	for (int i = 0; i < 26; i++) {
		TrieNode* child = root->getChild(i);
		if (child != nullptr) {
			displayTrieHelper(words, *child, "");
		}
	}
	for (std::string word : words) {
		std::cout << word << std::endl;
	}
}

 

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include "Trie.h"


using namespace std;


int main() {
	Trie trie1;
	trie1.insert("apple");
	cout << trie1.search("apple") << endl;   // return True
	cout << trie1.search("app") << endl;     // return False
	cout << trie1.startsWith("app") << endl; // return True
	trie1.insert("app");
	cout << trie1.search("app") << endl;   // return True
	
	Trie trie2(trie1);
	cout << trie2.search("apple") << endl;   // return True
	cout << trie2.search("app") << endl;     // return True
	cout << trie2.startsWith("app") << endl; // return True
	cout << trie2.search("app") << endl;   // return True
	
	vector<Trie> vec;
	vec.push_back(trie2);
	cout << vec[0].search("apple") << endl;
	
	displayTrie(trie1);
	
	Trie trie3;
	trie3 = trie1;
	displayTrie(trie3);
	
}