DEV Community

Prashant Mishra
Prashant Mishra

Posted on • Originally published at leetcode.com

Trie

Implementing Trie data structure

Striver explanation of trie data structure

class Node{
    Node [] node = new Node[26];
    boolean flag;
    public Node(){

    }
    public boolean containsKey(char c){
        return node[c-'a']!=null;
    }
    public void put(char c, Node n){
        node[c-'a']  = n;
    }
    public Node get(char c){
        return node[c-'a'];
    }
    public void setFlag() {
        this.flag = true;
    }
    public boolean getFlag(){
        return this.flag;
    }
}

class Trie {
    Node root;
    public Trie() {
        root = new Node();
    }
    //will take tc : O(len) of the word
    public void insert(String word) {
        Node node  = root;
        for(int i =0;i<word.length();i++){
            if(!node.containsKey(word.charAt(i))){
                node.put(word.charAt(i),new Node());
            }
            node = node.get(word.charAt(i));
        }
        node.setFlag();
    }
    //will take tc : O(len) of the word
    public boolean search(String word) {
        Node node = root;
        for(int i =0;i<word.length();i++){
            if(!node.containsKey(word.charAt(i))){
                return false;
            }
            node = node.get(word.charAt(i));
        }
        return node.getFlag();
    }
    //will take tc : O(len) of the prefix
    public boolean startsWith(String prefix) {
         Node node = root;
        for(int i =0;i<prefix.length();i++){
            if(!node.containsKey(prefix.charAt(i))){
                return false;
            }
            node = node.get(prefix.charAt(i));
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */
Enter fullscreen mode Exit fullscreen mode

Trie data structure II

striver's explanation for better understanding

import java.util.* ;
import java.io.*; 

class Node {
    Node node[] = new Node[26];
    int endWith = 0;// will keep track of no. of words ending with this word
    int countPrefix=0;// will keep track of no. of words starting with this word
    public Node(){

    }
    public boolean containsKey(char c){
        return node[c-'a']!=null;
    }
    public void put(char c, Node n){
        node[c-'a'] = n;
    }
    public Node get(char c){
        return node[c-'a'];
    }
    public void incrementCountPrefix() {
        ++this.countPrefix;
    }
    public void decrementCountPrefix(){
        --this.countPrefix;
    }
    public void incrementEndWith(){
        ++this.endWith;
    }
    public void deleteEndWith(){
        --this.endWith;
    }
    public int getCountPrefix(){
        return this.countPrefix;
    }
    public int getEndWith(){
        return this.endWith;
    }


}
public class Trie {
    Node root;
    public Trie() {
        // Write your code here.
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for(int i =0;i<word.length();i++){
            if(!node.containsKey(word.charAt(i))){
                node.put(word.charAt(i),new Node());
            }
            node = node.get(word.charAt(i));
            node.incrementCountPrefix();
        }
        node.incrementEndWith();
    }

    public int countWordsEqualTo(String word) {
        // Write your code here. 
        Node node = root;
        for(int i=0;i<word.length();i++){
            if(node.containsKey(word.charAt(i))){
                node  = node.get(word.charAt(i));
            }
            else return 0;

        }
        return node.getEndWith();//this will tell how many strings are 
        //ending with given word

    }



    public int countWordsStartingWith(String word) { 
        Node node = root;
        for(int i=0;i<word.length();i++){
            if(node.containsKey(word.charAt(i))){
                node  = node.get(word.charAt(i));
            }
            else return 0;

        }
        return  node.getCountPrefix(); // it will tell how many strings are starting 
        //with given word;
    }

    public void erase(String word) {
         Node node = root;
        for(int i =0;i<word.length();i++){
            if(node.containsKey(word.charAt(i))){
                node = node.get(word.charAt(i));
                node.decrementCountPrefix();
            }
            else return;


        }
        node.deleteEndWith();
    }

}

Enter fullscreen mode Exit fullscreen mode

Complete String

// tc : O(n*l)

import java.util.* ;
import java.io.*; 

class Node{
    Node[] node = new Node[26];
    boolean flag;
    public Node(){}
    public void put(char c , Node n){
        node[c-'a'] = n;
    }
    public boolean containsKey(char c){
        return node[c-'a']!=null;
    }
    public Node get(char c){
        return node[c-'a'];
    }
    public void setEnd(){
        this.flag = true;
    }
    public boolean isEnd(){
        return this.flag;
    }
}

class Trie{
    Node root;
    public Trie(){
        root = new Node();
    }
    public boolean checkIfPrefixPresent(String s){
      Node node = root;
      boolean flag= true;
      for(int i = 0;i<s.length();i++){
          char c = s.charAt(i);
          if(!node.containsKey(c)){
              return false;
          }
          node = node.get(c);
          flag = flag && node.isEnd(); // this will check if the substring is also a string from the list of strings
          //if(flag == false) return false; // this line will also work here because if any substring is not present as a string in the trie , then 
          // this string s won't be a complete string, and we can return false here only
      }
      return flag;
  }
  public void insert(String s){
    Node node = root;
    for(int i =0;i<s.length();i++){
        char c = s.charAt(i);
        if(!node.containsKey(c)){
            node.put(c, new Node());
        }
        node = node.get(c);
    }
    node.setEnd(); // setting end of the string as this is the 
          //end of the current string s 
  }
}
class Solution {
    static Node root;
  public static String completeString(int n, String[] a) {
      Trie trie = new Trie();
      //storing all the string in the trie data structure
      for(String s : a) trie.insert(s);
      //finding out the comeplete string among all the list of strings
      String completeString = "";
      for(String s : a){
          if(trie.checkIfPrefixPresent(s)){
              if(completeString.length() < s.length()){
                  completeString = s;
              }
              //lexographical selection : a.compareTo(b) =-1 if a < b lexographically 
              else if(completeString.length() == s.length() && s.compareTo(completeString) < 0){
                  completeString = s;
              }
          }
      }
      return completeString.equals("") ? "None":completeString;
  }
}
Enter fullscreen mode Exit fullscreen mode

Count distinct substring

Tc: O(n^2) for inserting different unique substring in
Trie data structure


import java.util.ArrayList;

public class Solution 
{
    Node root;
    static int count;
    public Solution(){
        root = new Node();
    }

    public static int countDistinctSubstrings(String s) 
    {
        count = 0;
        //    Write your code here.
        Solution sol = new Solution();
        for(int i =0;i< s.length();i++){
            String str = "";
            for (int j =i;j< s.length();j++){
                str = str+s.charAt(j);
                sol.insert(str);
            }
        }
        return count+1;
    }
    public void insert(String s){
        Node node = root;
        for(int i =0;i< s.length();i++){
            if(!node.containsKey(s.charAt(i))){
                node.put(s.charAt(i),new Node());
                count++;
            }
            node = node.get(s.charAt(i));
        }
        node.setFlag();
    }
}
class Node {
    Node node[] = new Node[26];
    boolean flag;
    public Node(){

    }
    public boolean containsKey(char c){
        return node[c-'a']!=null;
    }
    public Node get(char c){
        return node[c-'a'];
    }
    public void put(char c, Node n){
        node[c-'a'] = n;
    }
    public void setFlag(){
        this.flag = true;
    }
    public boolean getFlag(){
        return this.flag;
    }
}
Enter fullscreen mode Exit fullscreen mode

Maximum XOR


// for more understanding refer : https://www.youtube.com/watch?v=EIhAwfHubE8&list=PLgUwDviBIf0pcIDCZnxhv0LkHf5KzG9zp&index=6
import java.util.ArrayList;
public class Solution 
{
    public static int maxXOR(int n, int m, ArrayList<Integer> arr1, ArrayList<Integer> arr2) 
    {
        Trie trie = new Trie();
        //lets put arr1 nums in the array
        for(int num : arr1){
            trie.insert(num);
        }

        //now find all the xor between arr2 and arr1 numbers 
        int maxExOr = 0;
        for(int num : arr2){
            maxExOr = Integer.max(maxExOr,trie.getMaxExor(num));
        }
        return maxExOr;  

    }
}
class Node{
    Node node[] = new Node[2];
    public boolean containsKey(int bit){
        return node[bit]!=null;
    }
    public void put(int bit, Node n){
        node[bit] = n;
    }
    public Node get(int bit){
        return node[bit];
    }
}
class Trie{
    Node root;
    public Trie(){
        root = new Node();
    }
    public void insert(int num){
        Node node  = root;
        for(int i = 31;i>=0;i--){
            int  bit = (num>>i)&1;// this will check if the bit at index i 
            //is set or not (basically this helps putting the num bits in 
            //the trie from right bit to left bit)
            if(!node.containsKey(bit)){
                node.put(bit,new Node());
            }
            node = node.get(bit);
        }
    }
    public int getMaxExor(int  num){
        Node node = root;
        int maxNumber = 0;
        for(int i =31;i>=0;i--){
            int bit = (num>>i) &1;
            if(!node.containsKey(1-bit)){// since we have to find opposite of bit at index i to get the max exor
                node = node.get(bit);// if we don't have reverse bit we have to settle for what we have
            }
            else{
                node = node.get(1-bit);
                maxNumber = maxNumber | 1<<i; // this will add the bit at ith index in the maxNumber
            }   
        }
        return maxNumber;
    }
}
Enter fullscreen mode Exit fullscreen mode

Max xor with an element of the array

Brute force approach:

//tc :O(n*m) : where n is length of the queries list, and m is the size of the arr list
import java.util.*;

public class Solution {
    public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {

        ArrayList<Integer> result = new ArrayList<>();
        for( int i =0;i<queries.size();i++){
            int X = queries.get(i).get(0);
            int A = queries.get(i).get(1);
            int max = -1;
            for(Integer j : arr){
                if(j<=A){
                    max = Integer.max(max,X^j);
                }
            }
            result.add(max);
        }
        return result;

    }
}
Enter fullscreen mode Exit fullscreen mode

Trie approach:

import java.util.*;

class QueryDetails{
    int xi;
    int ai;
    int index;
    public QueryDetails(int x ,int a, int i){
        this.xi = x;
        this.ai = a;
        this.index = i;
    }
    public int getX(){
        return xi;
    }
    public int getA(){
        return ai;
    }
    public int getIndex(){
        return index;
    }
}
public class Solution {
    public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
        // Write your code here.
        Trie trie = new Trie();
        Collections.sort(arr);
        PriorityQueue<QueryDetails> q = new PriorityQueue<>((a,b)-> a.getA()-b.getA());
        for(int i =0;i<queries.size();i++){
            q.add(new QueryDetails(queries.get(i).get(0),queries.get(i).get(1),i));
        }
        ArrayList<Integer> list  = new ArrayList<>();
        for(int i =0;i< queries.size();i++){
            list.add(-1); //intialization;// that is bound to change later
        }

        int indexOfArr =0;
        while(!q.isEmpty()){
            QueryDetails query = q.remove();
            int x = query.getX();
            int a = query.getA();
            int index = query.getIndex();
            int max = -1;
            while(indexOfArr<arr.size() && arr.get(indexOfArr)<=a){
                trie.insert(arr.get(indexOfArr));
                indexOfArr++;
            }
            //edge case what if  starting value of arr(list) is greater that a in that case we can not have any exor with x(since the condition arr.get(i)<=a is not satisfied )
            if(indexOfArr==0) list.set(index, -1);
            else{
                max =  trie.getMaxExor(x); 
                list.set(index,max);
            }

        }
        return list;
    }
}
class Node{
    Node node[] = new Node[2];
    public boolean containsKey(int bit){
        return node[bit]!=null;
    }
    public void put(int bit, Node n){
        node[bit] = n;
    }
    public Node get(int bit){
        return node[bit];
    }
}
class Trie{
    Node root;
    public Trie(){
        root = new Node();
    }
    public void insert(int num){
        Node node  = root;
        for(int i = 31;i>=0;i--){
            int  bit = (num>>i)&1;// this will check if the bit at index i
            //is set or not (basically this helps putting the num bits in
            //the trie from right bit to left bit)
            if(!node.containsKey(bit)){
                node.put(bit,new Node());
            }
            node = node.get(bit);
        }
    }
    public int getMaxExor(int  num){
        Node node = root;
        int maxNumber = 0 ;
        for(int i =31;i>=0;i--){
            int bit = (num>>i) &1;
            if(node!=null && !node.containsKey(1-bit)){// since we have to find opposite of bit at index i to get the max exor
                node = node.get(bit);// if we don't have reverse bit we have to settle for what we have
            }
            else{
                node = node.get(1-bit);
                maxNumber = maxNumber | 1<<i; // this will add the bit at ith index in the maxNumber
            }
        }
        return maxNumber;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)