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);
*/
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();
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
Top comments (0)