티스토리 뷰
leetcode.com/problems/implement-trie-prefix-tree/
Implement Trie (Prefix Tree) - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Trie는 문자열 탐색 알고리즘 중 하나.
root 노드에서부터 자식 노드를 따라 내려가며 문자 하나하나 완성시켜나가는 알고리즘.
insert함수를 실행하면 Trie에 문자열을 Trie알고리즘에 따라 입력
search함수를 실행하면 parameter로 받아온 문자열이 있을 경우 true, 없을 경우 false반환
startWith함수를 실행하면 parameter로 시작하는 문자열이 있을 경우 true, 없을 경우 false반환
typescript code
class Trie{
private root : Object;
private end : string;
constructor() {
this.root = {};
this.end = "*";
}
public insert(word : string){
let currentNode : Object = this.root;
for(let i = 0; i < word.length; i++) {
!currentNode[word[i]] && ( currentNode[word[i]] = {} );
currentNode = currentNode[word[i]];
}
currentNode[this.end] = true;
}
public search(word : string) : boolean{
let currentNode : Object = this.root;
for(let i = 0; i < word.length; i++) {
if(!currentNode[word[i]]) return false;
currentNode = currentNode[word[i]];
if(i === word.length - 1){
if(currentNode[this.end]) return true;
}
}
return false;
}
public startsWith(prefix : string){
let currentNode : Object = this.root;
for(let i = 0; i < prefix.length; i++) {
if(!currentNode[prefix[i]]) return false;
currentNode = currentNode[prefix[i]];
}
return Object.keys(currentNode).length !== 0;
}
}
rust code
use std::collections::HashMap;
#[derive(Debug)]
struct Node{
is_word: bool,
next: HashMap<char, Node>
}
impl Node{
fn new() -> Self {
Node {
is_word: false,
next: HashMap::new()
}
}
}
#[derive(Debug)]
struct Trie {
root: Node
}
impl Trie {
fn moving<T> (t : T) -> T{
t
}
fn new() -> Self {
Trie{ root: Node::new() }
}
fn insert(&mut self, word: String) {
let mut current = &mut self.root;
for w in word.chars(){
current = Trie::moving(current).next.entry(w).or_insert(Node::new());
}
if !current.is_word{
current.is_word = true;
}
}
fn search(&mut self, word: String) -> bool {
let mut current = &mut self.root;
for w in word.chars(){
if let Some(_) = current.next.get(&w){
current = Trie::moving(current).next.entry(w).or_insert(Node::new());
}else{
return false;
}
}
current.is_word
}
fn starts_with(&mut self, prefix: String) -> bool {
let mut current = &mut self.root;
for w in prefix.chars(){
if let Some(_) = current.next.get(&w){
current = Trie::moving(current).next.entry(w).or_insert(Node::new());
}else{
return false;
}
}
true
}
}rust코드 input data 및 실행 결과
pub fn run(){
let mut obj = Trie::new();
obj.insert("apple".parse().unwrap());
obj.insert("cat".parse().unwrap());
obj.insert("dog".parse().unwrap());
obj.insert("boat".parse().unwrap());
obj.insert("plane".parse().unwrap());
obj.insert("bottle".parse().unwrap());
obj.insert("note".parse().unwrap());
obj.insert("compiler".parse().unwrap());
println!("{:#?}", obj);
}Trie {
root: Node {
is_word: false,
next: {
'p': Node {
is_word: false,
next: {
'l': Node {
is_word: false,
next: {
'a': Node {
is_word: false,
next: {
'n': Node {
is_word: false,
next: {
'e': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
},
},
'd': Node {
is_word: false,
next: {
'o': Node {
is_word: false,
next: {
'g': Node {
is_word: true,
next: {},
},
},
},
},
},
'b': Node {
is_word: false,
next: {
'o': Node {
is_word: false,
next: {
'a': Node {
is_word: false,
next: {
't': Node {
is_word: true,
next: {},
},
},
},
't': Node {
is_word: false,
next: {
't': Node {
is_word: false,
next: {
'l': Node {
is_word: false,
next: {
'e': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
},
},
},
},
'a': Node {
is_word: false,
next: {
'p': Node {
is_word: false,
next: {
'p': Node {
is_word: false,
next: {
'l': Node {
is_word: false,
next: {
'e': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
},
},
'n': Node {
is_word: false,
next: {
'o': Node {
is_word: false,
next: {
't': Node {
is_word: false,
next: {
'e': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
'c': Node {
is_word: false,
next: {
'o': Node {
is_word: false,
next: {
'm': Node {
is_word: false,
next: {
'p': Node {
is_word: false,
next: {
'i': Node {
is_word: false,
next: {
'l': Node {
is_word: false,
next: {
'e': Node {
is_word: false,
next: {
'r': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
},
},
},
},
},
},
'a': Node {
is_word: false,
next: {
't': Node {
is_word: true,
next: {},
},
},
},
},
},
},
},
}'알고리즘 문제 풀이' 카테고리의 다른 글
| [알고리즘문제] 릿코드 Valid Parentheses (0) | 2021.05.08 |
|---|---|
| [알고리즘문제] 릿코드 Word Search II (0) | 2021.05.07 |
| [알고리즘문제] 릿코드 Course Schedule II (0) | 2021.05.02 |
| [알고리즘문제] 릿코드 Number of Provinces (0) | 2021.04.30 |
| [알고리즘문제] 릿코드 Rotting Oranges (0) | 2021.04.28 |