This is a JSFiddle assignment and must be completed at jsfiddle.net and include

Question

This is a JSFiddle assignment and must be completed at jsfiddle.net and include both the HTML and Java sections

Implement a TRIE that has both the functions AddToTRIE and CheckSpelling.

Once you have created the TRIE add the words (hard code) I, in, into, inlet, inn, inner, innate, ink. These are good words to use to test your TRIE

Create an interface that has one text box for entry and 2 buttons - Add To Dictionary and Spell Check. They should ad the word to the TRIE (feedback - word added) and check the word against the TRIE and return in the word was in or not in the dictionary.

Explanation / Answer

class TrieNode {
char c;
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isLeaf;

public TrieNode() {}

public TrieNode(char c){
this.c = c;
}
}
public class Trie {
private TrieNode root;

public Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
public void insert(String word) {
HashMap<Character, TrieNode> children = root.children;

for(int i=0; i<word.length(); i++){
char c = word.charAt(i);

TrieNode t;
if(children.containsKey(c)){
t = children.get(c);
}else{
t = new TrieNode(c);
children.put(c, t);
}

children = t.children;

//set leaf node
if(i==word.length()-1)
t.isLeaf = true;
}
}

// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode t = searchNode(word);

if(t != null && t.isLeaf)
return true;
else
return false;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if(searchNode(prefix) == null)
return false;
else
return true;
}

public TrieNode searchNode(String str){
Map<Character, TrieNode> children = root.children;
TrieNode t = null;
for(int i=0; i<str.length(); i++){
char c = str.charAt(i);
if(children.containsKey(c)){
t = children.get(c);
children = t.children;
}else{
return null;
}
}

return t;
}
}
Java Solution 2 - Improve Performance by Using an Array

Each trie node can only contains 'a'-'z' characters. So we can use a small array to store the character.

class TrieNode {
TrieNode[] arr;
boolean isEnd;
// Initialize your data structure here.
public TrieNode() {
this.arr = new TrieNode[26];
}

}

public class Trie {
private TrieNode root;

public Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
for(int i=0; i<word.length(); i++){
char c = word.charAt(i);
int index = c-'a';
if(p.arr[index]==null){
TrieNode temp = new TrieNode();
p.arr[index]=temp;
p = temp;
}else{
p=p.arr[index];
}
}
p.isEnd=true;
}

// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode p = searchNode(word);
if(p==null){
return false;
}else{
if(p.isEnd)
return true;
}

return false;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = searchNode(prefix);
if(p==null){
return false;
}else{
return true;
}
}

public TrieNode searchNode(String s){
TrieNode p = root;
for(int i=0; i<s.length(); i++){
char c= s.charAt(i);
int index = c-'a';
if(p.arr[index]!=null){
p = p.arr[index];
}else{
return null;
}
}

if(p==root)
return null;

return p;
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.