Skip to content

Instantly share code, notes, and snippets.

@hhimanshu
Created January 29, 2016 15:35
Show Gist options
  • Save hhimanshu/2396005184e465e0930e to your computer and use it in GitHub Desktop.
Save hhimanshu/2396005184e465e0930e to your computer and use it in GitHub Desktop.
R-Way Tries (Leetcode)
import java.io.*;
import java.util.*;
/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/
class Solution {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("abc");
trie.insert("abd");
trie.insert("abe");
System.out.println("abc exists? " + trie.search("abc"));
System.out.println("abd exists? " + trie.search("abd"));
System.out.println("abe exists? " + trie.search("abe"));
System.out.println("aba exists? " + trie.search("aba"));
System.out.println("startsWith(ab) exists? " + trie.startsWith("ab"));
System.out.println("startsWith(abc) exists? " + trie.startsWith("abc"));
}
}
class TrieNode {
private boolean value;
public static final int R = 256;
private TrieNode[] next = new TrieNode[R];
public TrieNode() {
}
public TrieNode[] getNext() {
return next;
}
public void setValue(boolean value) {
this.value = value;
}
public boolean getValue() {
return value;
}
}
class Trie {
private TrieNode root;
public Trie() {
//root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
root = insert(root, word, 0);
}
private TrieNode insert(TrieNode node, String word, int d) {
if (node == null) {
node = new TrieNode();
}
if (d == word.length()) {
node.setValue(true);
return node;
}
char c = word.charAt(d);
node.getNext()[c] = insert(node.getNext()[c], word, d + 1);
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = search(root, word, 0);
if (node != null && node.getValue()) {
return true;
}
return false;
}
private TrieNode search(TrieNode node, String word, int d) {
if (node == null) {
return null;
}
if (d == word.length()) {
return node;
}
char c = word.charAt(d);
return search(node.getNext()[c], word, d + 1);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = search(root, prefix, 0);
if (node == null) {
return false;
}
for(int c = 0; c < TrieNode.R; c ++) {
if(node.getNext()[c] != null) {
return true;
}
}
return false;
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment