[LeetCode] 208 - Implement Trie (Prefix Tree)

문제

• 링크: https://leetcode.com/problems/implement-trie-prefix-tree
• 난이도: Medium
• 태그: 해시 테이블, 문자열, 디자인, 트라이
• 결과: Time: 10 ms (96.54%), Space: 62.70 MB (7.64%)

풀이

class Trie
{
public:
	Trie()
	{
        mRoot = make_unique<Node>();
	}

	void insert(string word)
	{
		Node* curNode = mRoot.get();
		for (char c : word)
		{
            auto& child = curNode->children[c - 'a'];
    		if (child == nullptr)
			{
				child = make_unique<Node>();
			}

			curNode = child.get();
		}

		curNode->isWord = true;
	}

	bool search(string word)
	{
		Node* curNode = mRoot.get();
		for (char c : word)
		{
            auto& child = curNode->children[c - 'a'];
			if (child == nullptr)
			{
				return false;
			}

			curNode = child.get();
		}

		return curNode->isWord;
	}

	bool startsWith(string prefix)
	{
		Node* curNode = mRoot.get();
		for (char c : prefix)
		{
            auto& child = curNode->children[c - 'a'];
			if (child == nullptr)
			{
				return false;
			}

			curNode = child.get();
		}

		return true;
	}

private:
	struct Node
	{
		bool isWord = false;
		unique_ptr<Node> children[26];
	};

	unique_ptr<Node> mRoot;
};

트라이를 구현하는 문제다. 시키는대로 만들었다. 처음에는 Node의 멤버에 unordered_map을 사용했는데, 성능이 잘 안나와서 영어 소문자 입력만 들어온다는 사실을 이용해 길이 26짜리 고정 배열을 사용했다. new/delete 직접 하기 귀찮아서 RAII로 관리되도록 unique_ptr을 사용했다.

배운 점과 후기

트라이를 알고리즘 문제에 맞도록 변형해서 구현하는 것 말고 정말 prefix tree로서 제대로 구현한 건 처음이었다. 그래도 개념만 알고 있으면 구현은 간단하다.

이 포스트는 달레 스터디(5주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.