Need assistance with Trie class and using it as a dictionary to perform spell-ch

Question

Need assistance with Trie class and using it as a dictionary to perform spell-checking. Check if a key (string) exists in the trie, look at the string character by character while moving from node to node starting from the root. If we found the node representing the given string, we can check if it represents a real key, if it is, add should return false indicating the key is already in the set; if it is not, we can simply mark it as a real key. On the other hand, if we encounter a null during the search, new nodes need to be added to the trie.

public class Trie extends AbstractSet<String> {

   private final char[] _alphabet;
   private Node _root;
   private int _size;
   private int _version;
  
   private class Node{
       Node[] links;
       boolean isWord;
       // do not add any other fields for Node!
      
       Node(boolean isword){
           links = new Node[_alphabet.length];
           isWord = isword;
       }
   }
  
   private boolean _report(String msg){
       System.err.println(msg);
       return false;
   }
  
   private int _reportNeg(String msg){
       System.err.println(msg);
       return -1;
   }
  
   private boolean _wellFormed(){
       // invariants:
       // 1. alphabet should not be null
       // 2. root should not be null
       // 3. for each node:
       // i. its links array is not null (even for a leaf node) and have same size as alphabet
       // ii. if it is a leaf node (except root), its isWord is true, i.e., it represents a real word, not just some prefix
       // iii. no link creates cycle
       // 4. size matches number of real words in the trie
      
       if(_alphabet == null) return _report("no alphabet");
       if(_root == null) return _report("root is null");
       int size = checkTrie();
       if(size < 0) return false;
       if(_size != size) return _report("size does not match number of real words");
       return true;
   }
  
   private int checkTrie(){
       // TODO helper method for invariant 3
       //
       // Perform a BFS on the trie starting from root, if any link points to a visited node, there is a cycle.
       // Along the BFS traversal, check 3. i) and ii) for each node.
       // Return the number of real words (if i-iii passed for all nodes, -1 otherwise).
       // This will help to check for #4.
   }
  
   public Trie(char[] alphabet){
       // TODO constructor
       assert _wellFormed() : "invariant fail at end of constructor";
   }
  
   //Our solution uses a helper method to find the index of a char in the alphabet array
   //and returns -1 if it is not in the alphabet, this is optional.
  
   @Override
   public boolean contains(Object o){
       assert _wellFormed() : "invaraiant fail at start of contains";
       if(!(o instanceof String)) return false;
       String s = (String) o;
       // TODO contains
   }
  
   @Override
   public boolean add(String s){
       assert _wellFormed() : "invaraiant fail at start of add";
       if(s == null) throw new IllegalArgumentException("word cannot be null");
       // TODO add
       // 1. if s is in the trie and is a word, do nothing
       // 2. if s is in the trie and is not a word, change it to a word
       // 3. if s is not in the trie and contains illegal characters, throw IllegalArgumentException
       // 4. if s is not in the trie and does not contain illegal characters, add it to the trie
       //
       // Note that in case 4, we may need to add multiple nodes to the trie.
       // Do not forget about size and version.
      
       assert _wellFormed() : "invaraiant fail at end of add";
       return true;
   }
  
   @Override
   public boolean remove(Object o){
       assert _wellFormed() : "invaraiant fail at start of remove";
       if(!(o instanceof String)) return false;
       String s = (String) o;
       boolean ret = true;
       // TODO remove
       // 1. if o is not in the trie, return false
       // 2. if o is in the trie but is not a word, return false
       // 3. if o is in the trie and is a word, set it to be a non-word
       // i. if the node contains o is not a leaf node, done
       // ii. if the node contains o is a leaf node, remove it;
       // this may make its parent into a non-word leaf node, in that case,
       // remove the parent and so on.
       //   
       // Our solution uses a recursive private helper method to handle the searching (move down)
       // and removing (move up).
       // Node doRemove(Node x, String s, int index)
       // It has the same flavor as the helper method replaceNode in the BST assignment, in the
       // sense that the caller would update its node with the return value of the subcall. The
       // index argument is to remember which character of s we are working on.
       //
       // The helper method also handles updating size (if found), then remove compares the old
       // size with the new size to determine its return value. You can use other methods/design
       // as long as the implementation is correct and efficient.
      
       assert _wellFormed() : "invaraiant fail at end of remove";
       return ret;
   }

Explanation / Answer

check if key is exist

if its not exist go to next step

while(key==exits)

true

if itss null

then come out from the loop

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

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