#include <stdbool.h>
#include <stdlib.h>
typedef struct Trie {
struct Trie *children[26];
bool isEnd;
} Trie;
Trie *trieCreate() { return calloc(1, sizeof(Trie)); }
void trieInsert(Trie *obj, char *word) {
Trie *cur = obj;
for (; *word; word++) {
int i = *word - 'a';
if (!cur->children[i])
cur->children[i] = trieCreate();
cur = cur->children[i];
}
cur->isEnd = true;
}
// returns the node reached by following s, or NULL if the path breaks
static Trie *walk(Trie *cur, const char *s) {
for (; *s && cur; s++)
cur = cur->children[*s - 'a'];
return cur;
}
bool trieSearch(Trie *obj, char *word) {
Trie *node = walk(obj, word);
return node && node->isEnd;
}
bool trieStartsWith(Trie *obj, char *prefix) { return walk(obj, prefix); }
void trieFree(Trie *obj) {
if (!obj)
return;
for (int i = 0; i < 26; i++)
trieFree(obj->children[i]);
free(obj);
}
#include <string>
using namespace std;
class Trie {
private:
struct Node {
Node *children[26] = {};
bool is_end = false;
};
Node *root;
void destroy(Node *n) {
if (!n)
return;
for (Node *c : n->children)
destroy(c);
delete n;
}
public:
Trie() { root = new Node(); }
~Trie() { destroy(root); }
void insert(string word) {
Node *cur = root;
for (char ch : word) {
int i = ch - 'a';
if (!cur->children[i])
cur->children[i] = new Node();
cur = cur->children[i];
}
cur->is_end = true;
}
bool search(string word) {
Node *cur = root;
for (char ch : word) {
cur = cur->children[ch - 'a'];
if (!cur)
return false;
}
return cur->is_end;
}
bool startsWith(string prefix) {
Node *cur = root;
for (char ch : prefix) {
cur = cur->children[ch - 'a'];
if (!cur)
return false;
}
return true;
}
};
package tries
type Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (t *Trie) Insert(word string) {
cur := t
for _, ch := range word {
i := ch - 'a'
if cur.children[i] == nil {
cur.children[i] = &Trie{}
}
cur = cur.children[i]
}
cur.isEnd = true
}
// walk returns the node reached by following s, or nil if the path breaks.
func (t *Trie) walk(s string) *Trie {
cur := t
for _, ch := range s {
cur = cur.children[ch-'a']
if cur == nil {
return nil
}
}
return cur
}
func (t *Trie) Search(word string) bool {
node := t.walk(word)
return node != nil && node.isEnd
}
func (t *Trie) StartsWith(prefix string) bool {
return t.walk(prefix) != nil
}
class Trie {
private static class Node {
Node[] children = new Node[26];
boolean isEnd;
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char ch : word.toCharArray()) {
int i = ch - 'a';
if (cur.children[i] == null)
cur.children[i] = new Node();
cur = cur.children[i];
}
cur.isEnd = true;
}
public boolean search(String word) {
Node node = walk(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
// returns the node reached by following s, or null if the path breaks
private Node walk(String s) {
Node cur = root;
for (char ch : s.toCharArray()) {
cur = cur.children[ch - 'a'];
if (cur == null)
return null;
}
return cur;
}
}
class Node {
constructor() {
this.children = new Map();
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new Node();
}
insert(word) {
let cur = this.root;
for (const ch of word) {
if (!cur.children.has(ch)) cur.children.set(ch, new Node());
cur = cur.children.get(ch);
}
cur.isEnd = true;
}
search(word) {
const node = this.walk(word);
return node !== null && node.isEnd;
}
startsWith(prefix) {
return this.walk(prefix) !== null;
}
// returns the node reached by following s, or null if the path breaks
walk(s) {
let cur = this.root;
for (const ch of s) {
cur = cur.children.get(ch);
if (!cur) return null;
}
return cur;
}
}
from typing import Optional
class Node:
def __init__(self):
self.children: dict[str, "Node"] = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
cur = self.root
for ch in word:
cur = cur.children.setdefault(ch, Node())
cur.is_end = True
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._walk(prefix) is not None
# returns the node reached by following s, or None if the path breaks
def _walk(self, s: str) -> Optional[Node]:
cur = self.root
for ch in s:
cur = cur.children.get(ch)
if not cur:
return None
return cur
#[derive(Default)]
struct Trie {
children: [Option<Box<Trie>>; 26],
is_end: bool,
}
impl Trie {
fn new() -> Self {
Self::default()
}
fn insert(&mut self, word: String) {
let mut cur = self;
for b in word.bytes() {
cur = cur.children[(b - b'a') as usize].get_or_insert_with(Default::default);
}
cur.is_end = true;
}
fn search(&self, word: String) -> bool {
self.walk(&word).is_some_and(|n| n.is_end)
}
fn starts_with(&self, prefix: String) -> bool {
self.walk(&prefix).is_some()
}
// returns the node reached by following s, or None if the path breaks
fn walk(&self, s: &str) -> Option<&Trie> {
let mut cur = self;
for b in s.bytes() {
cur = cur.children[(b - b'a') as usize].as_deref()?;
}
Some(cur)
}
}