Which case have I missed in my algorithm here?


  • 0
    C

    I know this code is not efficient but I just wanted to figure out which case, algorithmically, have I missed here?

    class TrieNode {
    // Initialize your data structure here.
    String[] data;
    int[] end;
    TrieNode[] pointers;
    public TrieNode() {
        data = new String[26];
        end = new int[26];
        Arrays.fill(end, 0);
        pointers = new TrieNode[26];
        Arrays.fill(pointers, null);
     }
    }
    
    public class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
     // Inserts a word into the trie.
     public void insert(String word) {
        TrieNode node = root;
        
        for(int i = 0; i< word.length(); i++)
        {
            int index = word.charAt(i) - 'a';
            node.data[index] = String.valueOf(word.charAt(i));
            
            
            if(node.pointers[index] != null)
                if(i == word.length() - 1)
                    node.end[index] = 1;
                else
                    node = node.pointers[index];
            else if(i != word.length() - 1)        
            {
                TrieNode new_node = new TrieNode();
                node.pointers[index] = new_node;
                node = new_node;
            }
            else
                node.end[index] = 1;
         }
        
      }
    
      // Returns if the word is in the trie.
      public boolean search(String word) {
         TrieNode node = root;
        
        if(word == null || word.length() == 0)
            return false;
        int index = 0;
        for(int i = 0; i< word.length(); i++)
        {
            if(node == null)
                return false;
                
            index = word.charAt(i) - 'a';
            
            if(node.data[index] != null)
                if(node.end[index] == 1)
                 {
                     if(i == word.length() - 1)
                        return true;
                    else
                        node = node.pointers[index];
                 }
                 else
                    node = node.pointers[index];
        }
        return false;
    }
    
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
               TrieNode node = root;
        
        if(prefix == null || prefix.length() == 0)
            return false;
        
        for(int i = 0; i< prefix.length(); i++)
        {
            if(node == null)
                return false;
                
            int index = prefix.charAt(i) - 'a';
            if(node.data[index] != null)
                node = node.pointers[index];
            else 
                return false;
        }
        
        return true;
     }
    }
    
    // Your Trie object will be instantiated and called as such:
    // Trie trie = new Trie();
    // trie.insert("somestring");
    // trie.search("key");

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.