Scribd
Upload
12 views4 pages

Java Trie Implementation Guide

The document provides a Java implementation of a Trie data structure, including methods for inserting and searching words, checking prefixes, and finding the longest word. It also includes additional functions for word breaking and counting nodes in the Trie. The main method demonstrates the insertion of words and the usage of search and prefix checking functionalities.

Uploaded by

Sukriti Kalyani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views4 pages

Java Trie Implementation Guide

The document provides a Java implementation of a Trie data structure, including methods for inserting and searching words, checking prefixes, and finding the longest word. It also includes additional functions for word breaking and counting nodes in the Trie. The main method demonstrates the insertion of words and the usage of search and prefix checking functionalities.

Uploaded by

Sukriti Kalyani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Tries

Java Code

Trie : Implementations, Insert & Search


public class Tries {
static class Node {
Node[] children = new Node[26];
boolean eow;

public Node() {
for (int i=0; i<26; i++) {
children[i] = null;
}
}
}

public static Node root = new Node();

public static void insert(String word) { //O(n)


int level = 0;
int len = [Link]();
int idx = 0;

Node curr = root;


for(; level<len; level++) {
idx = [Link](level)-'a';
if([Link][idx] == null) {
[Link][idx] = new Node();
}
curr = [Link][idx];
}
[Link] = true;
}

public static boolean search(String key) { //O(n)


int level = 0;
int len = [Link]();
int idx = 0;
Node curr = root;
for(; level<len; level++) {
idx = [Link](level)-'a';
if([Link][idx] == null) {
return false;
}
curr = [Link][idx];
}
return [Link] == true;
}

public static void main(String args[]) {


String words[] = {"the", "a", "there", "their", "any", "thee"};
for (String word : words) {
insert(word);
[Link]("inserted " + word);
}

[Link]("thee -> " + search("thee"));


[Link]("thor -> " + search("thor"));

[Link](startsWith("the"));
[Link](startsWith("thi"));
}
}

Question 1

public static boolean wordBreak(String key) {


int len = [Link]();

if(len == 0) {
return true;
}

for(int i=1; i<=len; i++) {


if( search([Link](0, i)) &&
wordBreak([Link](i)) ) {
return true;
}
}

return false;
}

Question 2

public static boolean startsWith(String prefix) {


Node curr = root;
for(int i=0; i<[Link](); i++) {
int idx = [Link](i)-'a';
if([Link][idx] == null) {
return false;
}
curr = [Link][idx];
}
return true;
}

Question 3

public static void longestWord(Node root, StringBuilder curr) {

for(int i=0; i<26; i++) {


if([Link][i] != null && [Link][i].eow == true) {
[Link]((char)(i+'a'));
if([Link]() > [Link]()) {
ans = [Link]();
}
longestWord([Link][i], curr);
[Link]([Link]()-1);
}
}
}

public static String ans = "";


Question 4

public static void buildTrie(String str) {


//insert all suffixes to Trie
root = new Node();
for(int i=0; i<[Link](); i++) {
insert([Link](i));
}
}

public static int countNodes(Node root) {


if(root == null) {
return 0;
}

int count = 0;
for(int i=0; i<26; i++) {
if([Link][i] != null) {
count+= countNodes([Link][i]);
}
}
return 1+count; //extra one for the self node
}

You might also like