Created
December 29, 2020 00:35
-
-
Save rosuH/dc5e6dfbdea8424b8bd2da94d26a2fc3 to your computer and use it in GitHub Desktop.
Trie
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.TreeMap; | |
public class Trie { | |
private class Node { | |
public boolean isWord; | |
public TreeMap<Character, Node> next; | |
public Node(boolean isWord) { | |
this.isWord = isWord; | |
next = new TreeMap<>(); | |
} | |
public Node() { | |
this(false); | |
} | |
} | |
private Node root; | |
private int size; | |
public Trie() { | |
root = new Node(); | |
size = 0; | |
} | |
public int getSize() { | |
return size; | |
} | |
public void add(String word) { | |
Node cur = root; | |
for (int i = 0; i < word.length(); i++) { | |
char c = word.charAt(i); | |
if (cur.next.get(c) == null) { | |
cur.next.put(c, new Node()); | |
} | |
cur = cur.next.get(c); | |
} | |
if (!cur.isWord) { | |
cur.isWord = true; | |
size++; | |
} | |
} | |
public boolean contains(String word) { | |
Node cur = root; | |
for (int i = 0; i < word.length(); i++) { | |
char c = word.charAt(i); | |
if (cur.next.get(c) == null) { | |
return false; | |
} | |
cur = cur.next.get(c); | |
} | |
return cur.isWord; | |
} | |
public boolean isPrefix(String prefix) { | |
Node cur = root; | |
for (int i = 0; i < prefix.length(); i++) { | |
char c = prefix.charAt(i); | |
if (cur.next.get(c) == null) { | |
return false; | |
} | |
cur = cur.next.get(c); | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment