Leetcode 208. Implement Trie(Prefix Tree)

문제 링크

https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150

문제 해석

• Trie 를 구현하라
• insert , search , startsWith 기능을 구현

문제 해결

• 단순 구현 문제
• 데이터 구조를 어떻게 할지 고민하자!
  => Dictionary (hashtable) 을 이용해서 해결
• 각 알파벳에 해당하는 key + 해당 트리에 구조에 해당하는 단어가 있는지 확인하는 value

슈도 코드

1. insert

trie = head
for element in word
	if trie[element] == null
		trie[element] = {}
	trie = trie[element]
trie[value] = 1

2. search

trie = head
for element in word
	if trie[element] ==null
		return false
	trie = trie[element]
if trie[value]==1
	return true
else
	return false

3. startsWith

trie = head
for element in word
	if trie[lement] == null
		return false
	trie = trie[element]
return true

결과

사담

• 원리는 이해하면 , 매우 간단한 트라이 라서 쉽다 생각했는데 , 자신이 구조 생각하고 하니 조금 생각했던 거 같다.
• 한번쯤은 풀어보면 좋은 문제

메모본

• 구현 문제이므로 생략

Writed By Obisidan