[TIL] 22-03-16

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2022년 3월 16일

TIL

목록 보기

74/104

알고리즘 스터디

백준 5020 전화번호 목록

백준 14425 문자열 집합

백준 14426 접두사 찾기

알고리즘 스터디

📌참고자료

트라이(Trie) 자료구조

트라이(Trie) 자료구조
https://www.youtube.com/watch?v=WooOuXIiRjE

트라이(Trie) C++ 구현

Trie (Insert and Search)
https://www.geeksforgeeks.org/trie-insert-and-search/

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

// C++ implementation of search and insert
// operations on Trie

const int ALPHABET_SIZE = 26;

// trie node
struct TrieNode{
	struct TrieNode *children[ALPHABET_SIZE];

	// isEndOfWord is true if the node represents
	// end of a word
	bool isEndOfWord;
};

// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void){
	struct TrieNode *pNode = new TrieNode;

	pNode->isEndOfWord = false;

	for (int i = 0; i < ALPHABET_SIZE; i++)
		pNode->children[i] = NULL;

	return pNode;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode *root, string key){
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			pCrawl->children[index] = getNode();

		pCrawl = pCrawl->children[index];
	}

	// mark last node as leaf
	pCrawl->isEndOfWord = true;
}

// Returns true if key presents in trie, else
// false
bool search(struct TrieNode *root, string key){
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			return false;

		pCrawl = pCrawl->children[index];
	}

	return (pCrawl->isEndOfWord);
}

// Driver
int main(){
	// Input keys (use only 'a' through 'z'
	// and lower case)
	string keys[] = { "the", "a", "there", "answer", "any", "by", "bye", "their" };
	int n = sizeof(keys) / sizeof(keys[0]);

	struct TrieNode *root = getNode();

	// Construct trie
	for (int i = 0; i < n; i++) 
		insert(root, keys[i]);

	// Search for different keys
	search(root, "the") ? cout << "Yes\n" : cout << "No\n";
	search(root, "these") ? cout << "Yes\n" : cout << "No\n";
	return 0;
}