Implement Trie

Medium

Python

class Trie:
    def __init__(self):
        self.children={}
        self.is_end=False
    def insert(self,word):
        node=self
        for c in word:
            if c not in node.children: node.children[c]=Trie()
            node=node.children[c]
        node.is_end=True
    def search(self,word):
        node=self
        for c in word:
            if c not in node.children: return False
            node=node.children[c]
        return node.is_end
    def starts_with(self,prefix):
        node=self
        for c in prefix:
            if c not in node.children: return False
            node=node.children[c]
        return True

Java

class Trie{
    java.util.Map<Character,Trie> children=new java.util.HashMap<>();
    boolean isEnd=false;
    public void insert(String word){
        Trie node=this;
        for(char c:word.toCharArray()){
            node.children.putIfAbsent(c,new Trie());
            node=node.children.get(c);
        } node.isEnd=true;
    }
    public boolean search(String word){
        Trie node=this;
        for(char c:word.toCharArray()){
            if(!node.children.containsKey(c)) return false;
            node=node.children.get(c);
        } return node.isEnd;
    }
    public boolean startsWith(String prefix){
        Trie node=this;
        for(char c:prefix.toCharArray()){
            if(!node.children.containsKey(c)) return false;
            node=node.children.get(c);
        } return true;
    }
}

Key Insight

Trie with hash maps. Python dict vs Java HashMap. Direct iteration vs toCharArray().

Python → Java Differences

Python dict vs Java HashMap
String iteration vs toCharArray()
'c not in dict' vs !containsKey()

Python

class Trie:
    def __init__(self):
        self.children={}
        self.is_end=False
    def insert(self,word):
        node=self
        for c in word:
            if c not in node.children: node.children[c]=Trie()
            node=node.children[c]
        node.is_end=True
    def search(self,word):
        node=self
        for c in word:
            if c not in node.children: return False
            node=node.children[c]
        return node.is_end
    def starts_with(self,prefix):
        node=self
        for c in prefix:
            if c not in node.children: return False
            node=node.children[c]
        return True

Java

class Trie{
    java.util.Map<Character,Trie> children=new java.util.HashMap<>();
    boolean isEnd=false;
    public void insert(String word){
        Trie node=this;
        for(char c:word.toCharArray()){
            node.children.putIfAbsent(c,new Trie());
            node=node.children.get(c);
        } node.isEnd=true;
    }
    public boolean search(String word){
        Trie node=this;
        for(char c:word.toCharArray()){
            if(!node.children.containsKey(c)) return false;
            node=node.children.get(c);
        } return node.isEnd;
    }
    public boolean startsWith(String prefix){
        Trie node=this;
        for(char c:prefix.toCharArray()){
            if(!node.children.containsKey(c)) return false;
            node=node.children.get(c);
        } return true;
    }
}

Algorithm Steps

1. Each node has children map
2. Insert char by char
3. Mark end of word

← Previous All OOP Next →