Trie.txt

------------------------------------------Trie-----------------------------------------------
-> Solutions are either on LeetCode or codestudio
-> Just Go through eclipse before this.
-----------------------------------------------------------------------------------------
1. Implement TrieI

//Trie Implementation-I

//-> in Trie we cannot predict the space complexity as every trie contains 26 and at worst its 26 ^26, but it doesn't happen as there is so much repition.

class Node {
	Node links[] = new Node[26];
	boolean flag = false;  //for ending character means upto that character forming word exists

	public Node() {

	}

	boolean containsKey(char ch) {
		return (links[ch - 'a'] != null);
	}

	Node get(char ch) {
		return links[ch - 'a'];
	}

	void put(char ch, Node node) {
		links[ch - 'a'] = node;
	}

	void setEnd() {
		flag = true;
	}

	boolean isEnd() {
		return flag;
	}
}

public class TrieI {
	private static Node root;

	// Initialize your data structure here

	TrieI() {
		root = new Node();
	}

	// Inserts a word into the trie

//	T: O(len of word)
	public static 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());
			}
			// moves to the reference node.
			node = node.get(word.charAt(i));
		}
		node.setEnd();
	}

	// Returns if the word is in the trie

//	T: O(len of word)
	public static boolean search(String word) {
		Node node = root;
		for (int i = 0; i < word.length(); i++) {
			if (!node.containsKey(word.charAt(i))) {
				return false;
			}
			// moves to the reference node.
			node = node.get(word.charAt(i));
		}
		if (node.isEnd()) {
			return true;
		}
		return false;
	}

	// Returns if there is any word in the trie that starts with the given prefix

//	T: O(len of word)
	public static boolean startsWith(String prefix) {
		Node node = root;
		for (int i = 0; i < prefix.length(); i++) {
			if (!node.containsKey(prefix.charAt(i))) {
				return false;
			}
			// moves to the reference node.
			node = node.get(prefix.charAt(i));
		}
		return true;
	}
}
-----------------------------------------------------------------------------------------
2. Implement TrieII


class Nodes {
	Nodes links[] = new Nodes[26];
	int cntEndWith = 0;
	int cntPrefix = 0;

	public Nodes() {
	}

	boolean containsKey(char ch) {
		return (links[ch - 'a'] != null);
	}

	Nodes get(char ch) {
		return links[ch - 'a'];
	}

	void put(char ch, Nodes node) {
		links[ch - 'a'] = node;

	}

	void increaseEnd() {
		cntEndWith++;
	}

	void increasePrefix() {
		cntPrefix++;
	}

	void deleteEnd() {
		cntEndWith--;
	}

	void reducePrefix() {
		cntPrefix--;
	}

	int getEnd() {
		return cntEndWith;
	}

	int getPrefix() {
		return cntPrefix;
	}
}

public class TrieII {
	private Nodes root;

	// Initialize your data structure here

	TrieII() {
		root = new Nodes();
	}

	// Inserts a word into the trie

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

	public int countWordsEqualTo(String word) {
		Nodes 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.getEnd();
	}

	public int countWordsStartingWith(String word) {
		Nodes 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.getPrefix();
	}

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

}
-----------------------------------------------------------------------------------------
3. Longest Word with All Prefixes

T: O(N * (avg length))

static class Node {
	Node links[] = new Node[26];
	boolean flag = false;

	public Node() {
	}

	boolean containsKey(char ch) {
		return (links[ch - 'a'] != null);
	}

	Node get(char ch) {
		return links[ch - 'a'];
	}

	void put(char ch, Node node) {
		links[ch - 'a'] = node;
	}

	void setEnd() {
		flag = true;
	}

	boolean isEnd() {
		return flag;
	}
}

 static class Trie {
	private Node root;

	// Initialize your data structure here

	Trie() {
		root = new Node();
	}

	// Inserts a word into the trie
	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());
			}
			// moves to the reference node.
			node = node.get(word.charAt(i));
		}
		node.setEnd();
	}
 
    public boolean checkIfAllPrefixExists(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));
                if(!node.isEnd()){
                    return false;
                } 
            }else return false;
        }
        return true;
    }
    
}
    
  public static String completeString(int n, String[] a) {
    	Trie obj = new Trie();
      
      	for(int i=0;i<n;i++){
            obj.insert(a[i]);
        }
      
      	String longest = "";
      
      for(int i=0;i<n;i++){
          if(obj.checkIfAllPrefixExists(a[i])){
              if(a[i].length()>longest.length()){
                  longest = a[i];
              }else if(a[i].length() == longest.length() && a[i].compareTo(longest)<0){ //checking for lexicographically smaller
          	  	  longest = a[i];	
              }	
          }
      }
      if(longest.equals(""))return "None";
      return longest;
  }
-----------------------------------------------------------------------------
4. Number of Distinct Substring in a String

static class Node {
	Node links[] = new Node[26];

	public Node() {
	}

	boolean containsKey(char ch) {
		return (links[ch - 'a'] != null);
	}

	Node get(char ch) {
		return links[ch - 'a'];
	}

	void put(char ch, Node node) {
		links[ch - 'a'] = node;
	}
}    

	public static int countDistinctSubstrings(String s) 
	{
        int n = s.length();
		Node root = new Node();
        int count=0;
        
        for(int i=0;i<n;i++){
            Node node = root;
            for(int j=i;j<n;j++){
                if(!node.containsKey(s.charAt(j))){
                    node.put(s.charAt(j),new Node());
                    count++;
                }
                   node=node.get(s.charAt(j));
            }
        }
        return count+1; //+1 for empty string
  }
-----------------------------------------------------------------------------
XOR category=>
->  In this type of problems we generally put all the number in the Trie in form of their Binary representation.
-> The comparison to find the max num by xor is that we try to set the current bit in the final answer in order to get max number.

for eg x = 8 => 01000
Numbers are
-> 9(01001)  8(01000)  7(00111)  5(00101)  4(00100)
=> n is the number which will be formed from the array of numbers.

-> x   : 0 1 0 0 0  
-> n   : 0 0 1 1 1      <- since for the first bit to set we couldn't find any opposite (here 1) so that its xor becomes 1 and set this bit so we continued.
-> ans : 0 1 1 1 1 = 15

5. Maximum Xor of two number in an array 
T: O(32*N)

class Node {
    Node links[] = new Node[2]; 
    
    public Node() {
    }
    boolean containsKey(int ind) {
        return (links[ind] != null); 
    }
    Node get(int ind) {
        return links[ind]; 
    }
    void put(int ind, Node node) {
        links[ind] = node; 
    }
}
class Trie {
    private static Node root; 

    //Initialize your data structure here

    Trie() {
        root = new Node(); 
    }


    //Inserts a word into the trie

    public static void insert(int num) {
        Node node = root;
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
            if(!node.containsKey(bit)) {
                node.put(bit, new Node()); 
            }
            node = node.get(bit); 
        }
    }
    
    public int getMax(int num) {

// here we are trying to set bit as 1 if possible for a given bit from left to maximize the xor
        Node node = root; 
        int maxNum = 0; 
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
	//checking if opposite bit is present or not for setting bit (xor operation)
            if(node.containsKey(1 - bit)) {
                maxNum = maxNum | (1<<i);   //setting the bit
                node = node.get( 1 - bit); 
            }
            else {
                node = node.get(bit); 
            }
        }
        return maxNum; 
    }
}
public class Solution 
{
// insert all the values from array 1 and now for every element of array 2 find its max xor. and last find the overall max xor.

	public static int maxXOR(int n, int m, ArrayList<Integer> arr1, ArrayList<Integer> arr2) 
	{
	    Trie trie = new Trie(); 
        for(int i = 0;i<n;i++) {
            trie.insert(arr1.get(i)); 
        }
        int maxi = 0; 
        for(int i = 0;i<m;i++) {
            maxi = Math.max(maxi, trie.getMax(arr2.get(i))); 
        }
        return maxi; 
	}
}
-----------------------------------------------------------------------------
6. Max Xor Queries (Problem link->https://www.codingninjas.com/codestudio/problems/max-xor-queries_1382020?utm_source=youtube&utm_medium=affiliate&utm_campaign=striver_tries_videos)

T: O(NLogN + QLogQ + Q*32 + N*32)

class Node {
    Node links[] = new Node[2]; 
    
    public Node() {
    }
    boolean containsKey(int ind) {
        return (links[ind] != null); 
    }
    Node get(int ind) {
        return links[ind]; 
    }
    void put(int ind, Node node) {
        links[ind] = node; 
    }
}
class Trie {
    private static Node root; 

    //Initialize your data structure here

    Trie() {
        root = new Node(); 
    }


    //Inserts a word into the trie

    public static void insert(int num) {
        Node node = root;
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
            if(!node.containsKey(bit)) {
                node.put(bit, new Node()); 
            }
            node = node.get(bit); 
        }
    }
    
    public int getMax(int num) {
        Node node = root; 
        int maxNum = 0; 
        for(int i = 31;i>=0;i--) {
            int bit = (num >> i) & 1; 
            if(node.containsKey(1 - bit)) {
                maxNum = maxNum | (1<<i);
                node = node.get( 1 - bit); 
            }
            else {
                node = node.get(bit); 
            }
        }
        return maxNum; 
    }
}
public class Solution {

// we are basically sorting accoding to the queries limit in increasing order in order to use the getMax(),
in this we are not maintaining the less than limit constraint.
then we just upto that limit and so on. in the trie 

    public static ArrayList<Integer> maxXorQueries(ArrayList<Integer> arr, ArrayList<ArrayList<Integer>> queries) {
         Collections.sort(arr); 
         ArrayList<ArrayList<Integer>> offlineQueries = new ArrayList<ArrayList<Integer>>(); 
         int m = queries.size(); 
         for(int i = 0;i<m;i++) {
             ArrayList<Integer> temp = new ArrayList<Integer>(); 
             temp.add(queries.get(i).get(1)); 
             temp.add(queries.get(i).get(0)); 
             temp.add(i);   //for query number to locate it in the result array.
             offlineQueries.add(temp); 
         }
         Collections.sort(offlineQueries, new Comparator<ArrayList<Integer>> () {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                return a.get(0).compareTo(b.get(0));
            }
        });
         int ind = 0;
         int n = arr.size(); 
         Trie trie = new Trie(); 
         ArrayList<Integer> ans = new ArrayList<Integer>(m); 
         for(int i = 0;i<m;i++) ans.add(-1); // so that it becomes an array.
         for(int i = 0;i<m;i++) {
             while(ind<n && arr.get(ind) <= offlineQueries.get(i).get(0)) {
                 trie.insert(arr.get(ind)); 
                 ind++; 
             }
             int queryInd = offlineQueries.get(i).get(2); 
             if(ind!=0) ans.set(queryInd, trie.getMax(offlineQueries.get(i).get(1)));
             else ans.set(queryInd, -1); 
         }
         return ans; 
    }
}
-----------------------------------------------------------------------------
7. Design Add and Search Words Data Structure

TC : O(∑ L) + O(26^X), where L is the length of words we are inserting in Trie, X is the length of word we are searching.
SC : O(∑ L)

class Node {
    HashMap<Character, Node> children;
    boolean isEnd;
    Node() {
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}

class WordDictionary {

    private Node root;
    
    public WordDictionary() {
        this.root = new Node();
    }
    
    public void addWord(String word) {
        Node curr = this.root;
        
        for(char ch : word.toCharArray()) {
            if(!curr.children.containsKey(ch))
                curr.children.put(ch, new Node());
            curr = curr.children.get(ch);
        }
        curr.isEnd = true;
    }
    
    public boolean search(String word) {
        return search(word, this.root, 0);
    }
    
    private boolean search(String word, Node curr, int index) {
        
        for(int i=index;i<word.length();i++) {
            char ch = word.charAt(i);
            if(ch == '.') {
                // look for the word ahead
                for(char c : curr.children.keySet()) {
                    Node trieNode = curr.children.get(c);
                    if(search(word, trieNode, i+1))
                        return true;
                }
                return false;
            } else {
                if(!curr.children.containsKey(ch))
                    return false;
                curr = curr.children.get(ch);
            }
        }
        return curr.isEnd;
    }
}

-----------------------------------------------------------------------------
8. Boggle subsequences
-> https://www.geeksforgeeks.org/boggle-set-2-using-trie/

-----------------------------------------------------------------------------
9. Prefix and Suffix Search (LC-745) (Hard)
-> Take "apple" as an example, we will insert add "apple{apple", "pple{apple", "ple{apple", "le{apple", "e{apple", "{apple" into the Trie Tree.
If the query is: prefix = "app", suffix = "le", we can find it by querying our trie for
"le { app".
We use '{' because in ASCii Table, '{' is next to 'z', so we just need to create new TrieNode[27] instead of 26. Also, compared with tradition Trie, we add the attribute weight in class TrieNode.

class TrieNode {
    TrieNode[] children;
    int weight;
    public TrieNode() {
        children = new TrieNode[27]; // 'a' - 'z' and '{'. 'z' and '{' are neighbours in ASCII table
        weight = 0;
    }
}

public class WordFilter {
    TrieNode root;
    public WordFilter(String[] words) {
        root = new TrieNode();
        for (int weight = 0; weight < words.length; weight++) {
            String word = words[weight] + "{";
            for (int i = 0; i < word.length(); i++) {
                TrieNode cur = root;
                cur.weight = weight;
    // add "apple{apple", "pple{apple", "ple{apple", "le{apple", "e{apple", "{apple" into the Trie Tree
                for (int j = i; j < 2 * word.length() - 1; j++) {
                    int k = word.charAt(j % word.length()) - 'a';
                    if (cur.children[k] == null)
                        cur.children[k] = new TrieNode();
                    cur = cur.children[k];
                    cur.weight = weight;
                }
            }
        }
    }
    public int f(String prefix, String suffix) {
        TrieNode cur = root;
        for (char c: (suffix + '{' + prefix).toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                return -1;
            }
            cur = cur.children[c - 'a'];
        }
        return cur.weight;
    }
}

-----------------------------------------------------------------------------
10. Search Suggestions System (LC-1268)

 //Rather than applying sort, just iterate over the 26 chars of alphabets.
    
    // TC : O(n * m + O(3) - to add 3 words + 26 * s * avg) 
    // where n is the products.length and m is the avg length of each product[i]
    // and s is the length of searhWord
    // SC : O(n * m)
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie obj = new Trie();
        for(String w : products)
            obj.addWord(w);
        
        List<List<String>> R = new ArrayList<>();
        Node curr = obj.root;
        for(char ch : searchWord.toCharArray()) {

            if(curr!=null)
            {
                curr = curr.children.get(ch);
                List<String> t = obj.search(curr, new ArrayList<String>());
                R.add(t);
            }
            // no suggestions
            else R.add(new ArrayList<String>());
        }
        return R;
    }
}

class Node {
    HashMap<Character, Node> children;
    boolean isEnd;
    String word;
    
    Node() {
        this.children = new HashMap<>();
        this.isEnd = false;
    }
}

class Trie {
    
    public Node root;
    
    Trie() {
        this.root = new Node();
    }
    
    public void addWord(String w) {
        Node curr = this.root;
        for(char ch : w.toCharArray()) {
            if(!curr.children.containsKey(ch))
                curr.children.put(ch, new Node());
            curr = curr.children.get(ch);
        }
        curr.isEnd = true;
        curr.word = w;
    }
    
    public List<String> search(Node curr, List<String> T) {
        if(T.size() == 3 || curr == null) {
            return T;
        }
        
        if(curr.isEnd) {
            T.add(curr.word);
        }
        
        for(char ch='a';ch<='z';ch++) {
            if(curr.children.containsKey(ch)) {
                search(curr.children.get(ch), T);
            }
        }
        return T;
    }
-----------------------------------------------------------------------------
11. Short Encoding of Words (LC-820)
-> time: O(NK), space: O(NK)
Let's get the deacription clear:
Given string list L1, construct a another string list L2, making every word in L1 be a suffix of a word in L2.
Return the minimum possible total length of words in L2
Input L1: ["time","me","bell"]
L2: ["time","bell"]

So the idea of trie is really straightforward. It will be even more obvious if it is sufix.
What we should do here is insert all reversed words to a trie.

class Solution {

class TrieNode {
    HashMap<Character, TrieNode> next = new HashMap<>();
    int depth;
}
    public int minimumLengthEncoding(String[] words) {
        TrieNode root = new TrieNode();
        List<TrieNode> leaves = new  ArrayList<TrieNode>();
        for (String w : new HashSet<>(Arrays.asList(words))) {
            TrieNode cur = root;
            for (int i = w.length() - 1; i >= 0; --i) {
                char j = w.charAt(i);
                if (!cur.next.containsKey(j)) cur.next.put(j, new TrieNode());
                cur = cur.next.get(j);
            }
            cur.depth = w.length() + 1;
            leaves.add(cur);
        }
        int res = 0;
        for (TrieNode leaf : leaves) if (leaf.next.isEmpty()) res += leaf.depth;
        return res;
    }
}

-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------