SDE Sheets Questions And Solutions (12 Part Series)
1 Arrays
2 Binary Tree
… 8 more parts…
3 Graph
4 String
5 Binary Search Tree
6 Greedy
7 Stack and Queue
8 DP
9 Heap(Priority Queue)
10 Recursion
11 Recursion and backtracking
12 Trie
Implementing Trie data structure
Striver explanation of trie data structure
<span>class</span> <span>Node</span><span>{</span><span>Node</span> <span>[]</span> <span>node</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span><span>boolean</span> <span>flag</span><span>;</span><span>public</span> <span>Node</span><span>(){</span><span>}</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span><span>}</span><span>public</span> <span>void</span> <span>setFlag</span><span>()</span> <span>{</span><span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span><span>}</span><span>public</span> <span>boolean</span> <span>getFlag</span><span>(){</span><span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span><span>}</span><span>}</span><span>class</span> <span>Trie</span> <span>{</span><span>Node</span> <span>root</span><span>;</span><span>public</span> <span>Trie</span><span>()</span> <span>{</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>//will take tc : O(len) of the word</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>node</span><span>.</span><span>setFlag</span><span>();</span><span>}</span><span>//will take tc : O(len) of the word</span><span>public</span> <span>boolean</span> <span>search</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>return</span> <span>false</span><span>;</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>return</span> <span>node</span><span>.</span><span>getFlag</span><span>();</span><span>}</span><span>//will take tc : O(len) of the prefix</span><span>public</span> <span>boolean</span> <span>startsWith</span><span>(</span><span>String</span> <span>prefix</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>prefix</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>prefix</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>return</span> <span>false</span><span>;</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>prefix</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>return</span> <span>true</span><span>;</span><span>}</span><span>}</span><span>/** * 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); */</span><span>class</span> <span>Node</span><span>{</span> <span>Node</span> <span>[]</span> <span>node</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span> <span>boolean</span> <span>flag</span><span>;</span> <span>public</span> <span>Node</span><span>(){</span> <span>}</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span> <span>}</span> <span>public</span> <span>void</span> <span>setFlag</span><span>()</span> <span>{</span> <span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span> <span>}</span> <span>public</span> <span>boolean</span> <span>getFlag</span><span>(){</span> <span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span> <span>}</span> <span>}</span> <span>class</span> <span>Trie</span> <span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>Trie</span><span>()</span> <span>{</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>//will take tc : O(len) of the word</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>node</span><span>.</span><span>setFlag</span><span>();</span> <span>}</span> <span>//will take tc : O(len) of the word</span> <span>public</span> <span>boolean</span> <span>search</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>return</span> <span>false</span><span>;</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>return</span> <span>node</span><span>.</span><span>getFlag</span><span>();</span> <span>}</span> <span>//will take tc : O(len) of the prefix</span> <span>public</span> <span>boolean</span> <span>startsWith</span><span>(</span><span>String</span> <span>prefix</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>prefix</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>prefix</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>return</span> <span>false</span><span>;</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>prefix</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>return</span> <span>true</span><span>;</span> <span>}</span> <span>}</span> <span>/** * 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); */</span>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
<span>import</span> <span>java.util.*</span> <span>;</span><span>import</span> <span>java.io.*</span><span>;</span><span>class</span> <span>Node</span> <span>{</span><span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span><span>int</span> <span>endWith</span> <span>=</span> <span>0</span><span>;</span><span>// will keep track of no. of words ending with this word</span><span>int</span> <span>countPrefix</span><span>=</span><span>0</span><span>;</span><span>// will keep track of no. of words starting with this word</span><span>public</span> <span>Node</span><span>(){</span><span>}</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span><span>}</span><span>public</span> <span>void</span> <span>incrementCountPrefix</span><span>()</span> <span>{</span><span>++</span><span>this</span><span>.</span><span>countPrefix</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>decrementCountPrefix</span><span>(){</span><span>--</span><span>this</span><span>.</span><span>countPrefix</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>incrementEndWith</span><span>(){</span><span>++</span><span>this</span><span>.</span><span>endWith</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>deleteEndWith</span><span>(){</span><span>--</span><span>this</span><span>.</span><span>endWith</span><span>;</span><span>}</span><span>public</span> <span>int</span> <span>getCountPrefix</span><span>(){</span><span>return</span> <span>this</span><span>.</span><span>countPrefix</span><span>;</span><span>}</span><span>public</span> <span>int</span> <span>getEndWith</span><span>(){</span><span>return</span> <span>this</span><span>.</span><span>endWith</span><span>;</span><span>}</span><span>}</span><span>public</span> <span>class</span> <span>Trie</span> <span>{</span><span>Node</span> <span>root</span><span>;</span><span>public</span> <span>Trie</span><span>()</span> <span>{</span><span>// Write your code here.</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>node</span><span>.</span><span>incrementCountPrefix</span><span>();</span><span>}</span><span>node</span><span>.</span><span>incrementEndWith</span><span>();</span><span>}</span><span>public</span> <span>int</span> <span>countWordsEqualTo</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>// Write your code here. </span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>else</span> <span>return</span> <span>0</span><span>;</span><span>}</span><span>return</span> <span>node</span><span>.</span><span>getEndWith</span><span>();</span><span>//this will tell how many strings are </span><span>//ending with given word</span><span>}</span><span>public</span> <span>int</span> <span>countWordsStartingWith</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>else</span> <span>return</span> <span>0</span><span>;</span><span>}</span><span>return</span> <span>node</span><span>.</span><span>getCountPrefix</span><span>();</span> <span>// it will tell how many strings are starting </span><span>//with given word;</span><span>}</span><span>public</span> <span>void</span> <span>erase</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>node</span><span>.</span><span>decrementCountPrefix</span><span>();</span><span>}</span><span>else</span> <span>return</span><span>;</span><span>}</span><span>node</span><span>.</span><span>deleteEndWith</span><span>();</span><span>}</span><span>}</span><span>import</span> <span>java.util.*</span> <span>;</span> <span>import</span> <span>java.io.*</span><span>;</span> <span>class</span> <span>Node</span> <span>{</span> <span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span> <span>int</span> <span>endWith</span> <span>=</span> <span>0</span><span>;</span><span>// will keep track of no. of words ending with this word</span> <span>int</span> <span>countPrefix</span><span>=</span><span>0</span><span>;</span><span>// will keep track of no. of words starting with this word</span> <span>public</span> <span>Node</span><span>(){</span> <span>}</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span> <span>}</span> <span>public</span> <span>void</span> <span>incrementCountPrefix</span><span>()</span> <span>{</span> <span>++</span><span>this</span><span>.</span><span>countPrefix</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>decrementCountPrefix</span><span>(){</span> <span>--</span><span>this</span><span>.</span><span>countPrefix</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>incrementEndWith</span><span>(){</span> <span>++</span><span>this</span><span>.</span><span>endWith</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>deleteEndWith</span><span>(){</span> <span>--</span><span>this</span><span>.</span><span>endWith</span><span>;</span> <span>}</span> <span>public</span> <span>int</span> <span>getCountPrefix</span><span>(){</span> <span>return</span> <span>this</span><span>.</span><span>countPrefix</span><span>;</span> <span>}</span> <span>public</span> <span>int</span> <span>getEndWith</span><span>(){</span> <span>return</span> <span>this</span><span>.</span><span>endWith</span><span>;</span> <span>}</span> <span>}</span> <span>public</span> <span>class</span> <span>Trie</span> <span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>Trie</span><span>()</span> <span>{</span> <span>// Write your code here.</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>node</span><span>.</span><span>incrementCountPrefix</span><span>();</span> <span>}</span> <span>node</span><span>.</span><span>incrementEndWith</span><span>();</span> <span>}</span> <span>public</span> <span>int</span> <span>countWordsEqualTo</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>// Write your code here. </span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>else</span> <span>return</span> <span>0</span><span>;</span> <span>}</span> <span>return</span> <span>node</span><span>.</span><span>getEndWith</span><span>();</span><span>//this will tell how many strings are </span> <span>//ending with given word</span> <span>}</span> <span>public</span> <span>int</span> <span>countWordsStartingWith</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span><span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>else</span> <span>return</span> <span>0</span><span>;</span> <span>}</span> <span>return</span> <span>node</span><span>.</span><span>getCountPrefix</span><span>();</span> <span>// it will tell how many strings are starting </span> <span>//with given word;</span> <span>}</span> <span>public</span> <span>void</span> <span>erase</span><span>(</span><span>String</span> <span>word</span><span>)</span> <span>{</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>word</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>word</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>node</span><span>.</span><span>decrementCountPrefix</span><span>();</span> <span>}</span> <span>else</span> <span>return</span><span>;</span> <span>}</span> <span>node</span><span>.</span><span>deleteEndWith</span><span>();</span> <span>}</span> <span>}</span>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
<span>// tc : O(n*l)</span><span>import</span> <span>java.util.*</span> <span>;</span><span>import</span> <span>java.io.*</span><span>;</span><span>class</span> <span>Node</span><span>{</span><span>Node</span><span>[]</span> <span>node</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span><span>boolean</span> <span>flag</span><span>;</span><span>public</span> <span>Node</span><span>(){}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span> <span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span><span>}</span><span>public</span> <span>void</span> <span>setEnd</span><span>(){</span><span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span><span>}</span><span>public</span> <span>boolean</span> <span>isEnd</span><span>(){</span><span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span><span>}</span><span>}</span><span>class</span> <span>Trie</span><span>{</span><span>Node</span> <span>root</span><span>;</span><span>public</span> <span>Trie</span><span>(){</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>public</span> <span>boolean</span> <span>checkIfPrefixPresent</span><span>(</span><span>String</span> <span>s</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>boolean</span> <span>flag</span><span>=</span> <span>true</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>char</span> <span>c</span> <span>=</span> <span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>);</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>c</span><span>)){</span><span>return</span> <span>false</span><span>;</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>c</span><span>);</span><span>flag</span> <span>=</span> <span>flag</span> <span>&&</span> <span>node</span><span>.</span><span>isEnd</span><span>();</span> <span>// this will check if the substring is also a string from the list of strings</span><span>//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 </span><span>// this string s won't be a complete string, and we can return false here only</span><span>}</span><span>return</span> <span>flag</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>s</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>char</span> <span>c</span> <span>=</span> <span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>);</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>c</span><span>)){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>c</span><span>,</span> <span>new</span> <span>Node</span><span>());</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>c</span><span>);</span><span>}</span><span>node</span><span>.</span><span>setEnd</span><span>();</span> <span>// setting end of the string as this is the </span><span>//end of the current string s </span><span>}</span><span>}</span><span>class</span> <span>Solution</span> <span>{</span><span>static</span> <span>Node</span> <span>root</span><span>;</span><span>public</span> <span>static</span> <span>String</span> <span>completeString</span><span>(</span><span>int</span> <span>n</span><span>,</span> <span>String</span><span>[]</span> <span>a</span><span>)</span> <span>{</span><span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span><span>//storing all the string in the trie data structure</span><span>for</span><span>(</span><span>String</span> <span>s</span> <span>:</span> <span>a</span><span>)</span> <span>trie</span><span>.</span><span>insert</span><span>(</span><span>s</span><span>);</span><span>//finding out the comeplete string among all the list of strings</span><span>String</span> <span>completeString</span> <span>=</span> <span>""</span><span>;</span><span>for</span><span>(</span><span>String</span> <span>s</span> <span>:</span> <span>a</span><span>){</span><span>if</span><span>(</span><span>trie</span><span>.</span><span>checkIfPrefixPresent</span><span>(</span><span>s</span><span>)){</span><span>if</span><span>(</span><span>completeString</span><span>.</span><span>length</span><span>()</span> <span><</span> <span>s</span><span>.</span><span>length</span><span>()){</span><span>completeString</span> <span>=</span> <span>s</span><span>;</span><span>}</span><span>//lexographical selection : a.compareTo(b) =-1 if a < b lexographically </span><span>else</span> <span>if</span><span>(</span><span>completeString</span><span>.</span><span>length</span><span>()</span> <span>==</span> <span>s</span><span>.</span><span>length</span><span>()</span> <span>&&</span> <span>s</span><span>.</span><span>compareTo</span><span>(</span><span>completeString</span><span>)</span> <span><</span> <span>0</span><span>){</span><span>completeString</span> <span>=</span> <span>s</span><span>;</span><span>}</span><span>}</span><span>}</span><span>return</span> <span>completeString</span><span>.</span><span>equals</span><span>(</span><span>""</span><span>)</span> <span>?</span> <span>"None"</span><span>:</span><span>completeString</span><span>;</span><span>}</span><span>}</span><span>// tc : O(n*l)</span> <span>import</span> <span>java.util.*</span> <span>;</span> <span>import</span> <span>java.io.*</span><span>;</span> <span>class</span> <span>Node</span><span>{</span> <span>Node</span><span>[]</span> <span>node</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span> <span>boolean</span> <span>flag</span><span>;</span> <span>public</span> <span>Node</span><span>(){}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span> <span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span> <span>}</span> <span>public</span> <span>void</span> <span>setEnd</span><span>(){</span> <span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span> <span>}</span> <span>public</span> <span>boolean</span> <span>isEnd</span><span>(){</span> <span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span> <span>}</span> <span>}</span> <span>class</span> <span>Trie</span><span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>Trie</span><span>(){</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>public</span> <span>boolean</span> <span>checkIfPrefixPresent</span><span>(</span><span>String</span> <span>s</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>boolean</span> <span>flag</span><span>=</span> <span>true</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>char</span> <span>c</span> <span>=</span> <span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>);</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>c</span><span>)){</span> <span>return</span> <span>false</span><span>;</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>c</span><span>);</span> <span>flag</span> <span>=</span> <span>flag</span> <span>&&</span> <span>node</span><span>.</span><span>isEnd</span><span>();</span> <span>// this will check if the substring is also a string from the list of strings</span> <span>//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 </span> <span>// this string s won't be a complete string, and we can return false here only</span> <span>}</span> <span>return</span> <span>flag</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>s</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>char</span> <span>c</span> <span>=</span> <span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>);</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>c</span><span>)){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>c</span><span>,</span> <span>new</span> <span>Node</span><span>());</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>c</span><span>);</span> <span>}</span> <span>node</span><span>.</span><span>setEnd</span><span>();</span> <span>// setting end of the string as this is the </span> <span>//end of the current string s </span> <span>}</span> <span>}</span> <span>class</span> <span>Solution</span> <span>{</span> <span>static</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>static</span> <span>String</span> <span>completeString</span><span>(</span><span>int</span> <span>n</span><span>,</span> <span>String</span><span>[]</span> <span>a</span><span>)</span> <span>{</span> <span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span> <span>//storing all the string in the trie data structure</span> <span>for</span><span>(</span><span>String</span> <span>s</span> <span>:</span> <span>a</span><span>)</span> <span>trie</span><span>.</span><span>insert</span><span>(</span><span>s</span><span>);</span> <span>//finding out the comeplete string among all the list of strings</span> <span>String</span> <span>completeString</span> <span>=</span> <span>""</span><span>;</span> <span>for</span><span>(</span><span>String</span> <span>s</span> <span>:</span> <span>a</span><span>){</span> <span>if</span><span>(</span><span>trie</span><span>.</span><span>checkIfPrefixPresent</span><span>(</span><span>s</span><span>)){</span> <span>if</span><span>(</span><span>completeString</span><span>.</span><span>length</span><span>()</span> <span><</span> <span>s</span><span>.</span><span>length</span><span>()){</span> <span>completeString</span> <span>=</span> <span>s</span><span>;</span> <span>}</span> <span>//lexographical selection : a.compareTo(b) =-1 if a < b lexographically </span> <span>else</span> <span>if</span><span>(</span><span>completeString</span><span>.</span><span>length</span><span>()</span> <span>==</span> <span>s</span><span>.</span><span>length</span><span>()</span> <span>&&</span> <span>s</span><span>.</span><span>compareTo</span><span>(</span><span>completeString</span><span>)</span> <span><</span> <span>0</span><span>){</span> <span>completeString</span> <span>=</span> <span>s</span><span>;</span> <span>}</span> <span>}</span> <span>}</span> <span>return</span> <span>completeString</span><span>.</span><span>equals</span><span>(</span><span>""</span><span>)</span> <span>?</span> <span>"None"</span><span>:</span><span>completeString</span><span>;</span> <span>}</span> <span>}</span>// 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
<span>import</span> <span>java.util.ArrayList</span><span>;</span><span>public</span> <span>class</span> <span>Solution</span><span>{</span><span>Node</span> <span>root</span><span>;</span><span>static</span> <span>int</span> <span>count</span><span>;</span><span>public</span> <span>Solution</span><span>(){</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>public</span> <span>static</span> <span>int</span> <span>countDistinctSubstrings</span><span>(</span><span>String</span> <span>s</span><span>)</span><span>{</span><span>count</span> <span>=</span> <span>0</span><span>;</span><span>// Write your code here.</span><span>Solution</span> <span>sol</span> <span>=</span> <span>new</span> <span>Solution</span><span>();</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>String</span> <span>str</span> <span>=</span> <span>""</span><span>;</span><span>for</span> <span>(</span><span>int</span> <span>j</span> <span>=</span><span>i</span><span>;</span><span>j</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>j</span><span>++){</span><span>str</span> <span>=</span> <span>str</span><span>+</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>j</span><span>);</span><span>sol</span><span>.</span><span>insert</span><span>(</span><span>str</span><span>);</span><span>}</span><span>}</span><span>return</span> <span>count</span><span>+</span><span>1</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>s</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span><span>count</span><span>++;</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span><span>}</span><span>node</span><span>.</span><span>setFlag</span><span>();</span><span>}</span><span>}</span><span>class</span> <span>Node</span> <span>{</span><span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span><span>boolean</span> <span>flag</span><span>;</span><span>public</span> <span>Node</span><span>(){</span><span>}</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span><span>}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>setFlag</span><span>(){</span><span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span><span>}</span><span>public</span> <span>boolean</span> <span>getFlag</span><span>(){</span><span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span><span>}</span><span>}</span><span>import</span> <span>java.util.ArrayList</span><span>;</span> <span>public</span> <span>class</span> <span>Solution</span> <span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>static</span> <span>int</span> <span>count</span><span>;</span> <span>public</span> <span>Solution</span><span>(){</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>public</span> <span>static</span> <span>int</span> <span>countDistinctSubstrings</span><span>(</span><span>String</span> <span>s</span><span>)</span> <span>{</span> <span>count</span> <span>=</span> <span>0</span><span>;</span> <span>// Write your code here.</span> <span>Solution</span> <span>sol</span> <span>=</span> <span>new</span> <span>Solution</span><span>();</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>String</span> <span>str</span> <span>=</span> <span>""</span><span>;</span> <span>for</span> <span>(</span><span>int</span> <span>j</span> <span>=</span><span>i</span><span>;</span><span>j</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>j</span><span>++){</span> <span>str</span> <span>=</span> <span>str</span><span>+</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>j</span><span>);</span> <span>sol</span><span>.</span><span>insert</span><span>(</span><span>str</span><span>);</span> <span>}</span> <span>}</span> <span>return</span> <span>count</span><span>+</span><span>1</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>String</span> <span>s</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>s</span><span>.</span><span>length</span><span>();</span><span>i</span><span>++){</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>))){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>),</span><span>new</span> <span>Node</span><span>());</span> <span>count</span><span>++;</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>s</span><span>.</span><span>charAt</span><span>(</span><span>i</span><span>));</span> <span>}</span> <span>node</span><span>.</span><span>setFlag</span><span>();</span> <span>}</span> <span>}</span> <span>class</span> <span>Node</span> <span>{</span> <span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>26</span><span>];</span> <span>boolean</span> <span>flag</span><span>;</span> <span>public</span> <span>Node</span><span>(){</span> <span>}</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>char</span> <span>c</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>];</span> <span>}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>char</span> <span>c</span><span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>c</span><span>-</span><span>'a'</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>setFlag</span><span>(){</span> <span>this</span><span>.</span><span>flag</span> <span>=</span> <span>true</span><span>;</span> <span>}</span> <span>public</span> <span>boolean</span> <span>getFlag</span><span>(){</span> <span>return</span> <span>this</span><span>.</span><span>flag</span><span>;</span> <span>}</span> <span>}</span>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
<span>// for more understanding refer : https://www.youtube.com/watch?v=EIhAwfHubE8&list=PLgUwDviBIf0pcIDCZnxhv0LkHf5KzG9zp&index=6</span><span>import</span> <span>java.util.ArrayList</span><span>;</span><span>public</span> <span>class</span> <span>Solution</span><span>{</span><span>public</span> <span>static</span> <span>int</span> <span>maxXOR</span><span>(</span><span>int</span> <span>n</span><span>,</span> <span>int</span> <span>m</span><span>,</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr1</span><span>,</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr2</span><span>)</span><span>{</span><span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span><span>//lets put arr1 nums in the array</span><span>for</span><span>(</span><span>int</span> <span>num</span> <span>:</span> <span>arr1</span><span>){</span><span>trie</span><span>.</span><span>insert</span><span>(</span><span>num</span><span>);</span><span>}</span><span>//now find all the xor between arr2 and arr1 numbers </span><span>int</span> <span>maxExOr</span> <span>=</span> <span>0</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>num</span> <span>:</span> <span>arr2</span><span>){</span><span>maxExOr</span> <span>=</span> <span>Integer</span><span>.</span><span>max</span><span>(</span><span>maxExOr</span><span>,</span><span>trie</span><span>.</span><span>getMaxExor</span><span>(</span><span>num</span><span>));</span><span>}</span><span>return</span> <span>maxExOr</span><span>;</span><span>}</span><span>}</span><span>class</span> <span>Node</span><span>{</span><span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>2</span><span>];</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>int</span> <span>bit</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>bit</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>int</span> <span>bit</span><span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>bit</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>int</span> <span>bit</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>bit</span><span>];</span><span>}</span><span>}</span><span>class</span> <span>Trie</span><span>{</span><span>Node</span> <span>root</span><span>;</span><span>public</span> <span>Trie</span><span>(){</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>int</span> <span>num</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span><span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)&</span><span>1</span><span>;</span><span>// this will check if the bit at index i </span><span>//is set or not (basically this helps putting the num bits in </span><span>//the trie from right bit to left bit)</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>bit</span><span>)){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>bit</span><span>,</span><span>new</span> <span>Node</span><span>());</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>}</span><span>}</span><span>public</span> <span>int</span> <span>getMaxExor</span><span>(</span><span>int</span> <span>num</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>int</span> <span>maxNumber</span> <span>=</span> <span>0</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span><span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)</span> <span>&</span><span>1</span><span>;</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>)){</span><span>// since we have to find opposite of bit at index i to get the max exor</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>// if we don't have reverse bit we have to settle for what we have</span><span>}</span><span>else</span><span>{</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>);</span><span>maxNumber</span> <span>=</span> <span>maxNumber</span> <span>|</span> <span>1</span><span><<</span><span>i</span><span>;</span> <span>// this will add the bit at ith index in the maxNumber</span><span>}</span><span>}</span><span>return</span> <span>maxNumber</span><span>;</span><span>}</span><span>}</span><span>// for more understanding refer : https://www.youtube.com/watch?v=EIhAwfHubE8&list=PLgUwDviBIf0pcIDCZnxhv0LkHf5KzG9zp&index=6</span> <span>import</span> <span>java.util.ArrayList</span><span>;</span> <span>public</span> <span>class</span> <span>Solution</span> <span>{</span> <span>public</span> <span>static</span> <span>int</span> <span>maxXOR</span><span>(</span><span>int</span> <span>n</span><span>,</span> <span>int</span> <span>m</span><span>,</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr1</span><span>,</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr2</span><span>)</span> <span>{</span> <span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span> <span>//lets put arr1 nums in the array</span> <span>for</span><span>(</span><span>int</span> <span>num</span> <span>:</span> <span>arr1</span><span>){</span> <span>trie</span><span>.</span><span>insert</span><span>(</span><span>num</span><span>);</span> <span>}</span> <span>//now find all the xor between arr2 and arr1 numbers </span> <span>int</span> <span>maxExOr</span> <span>=</span> <span>0</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>num</span> <span>:</span> <span>arr2</span><span>){</span> <span>maxExOr</span> <span>=</span> <span>Integer</span><span>.</span><span>max</span><span>(</span><span>maxExOr</span><span>,</span><span>trie</span><span>.</span><span>getMaxExor</span><span>(</span><span>num</span><span>));</span> <span>}</span> <span>return</span> <span>maxExOr</span><span>;</span> <span>}</span> <span>}</span> <span>class</span> <span>Node</span><span>{</span> <span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>2</span><span>];</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>int</span> <span>bit</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>bit</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>int</span> <span>bit</span><span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>bit</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>int</span> <span>bit</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>bit</span><span>];</span> <span>}</span> <span>}</span> <span>class</span> <span>Trie</span><span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>Trie</span><span>(){</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>int</span> <span>num</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span> <span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)&</span><span>1</span><span>;</span><span>// this will check if the bit at index i </span> <span>//is set or not (basically this helps putting the num bits in </span> <span>//the trie from right bit to left bit)</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>bit</span><span>)){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>bit</span><span>,</span><span>new</span> <span>Node</span><span>());</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span> <span>}</span> <span>}</span> <span>public</span> <span>int</span> <span>getMaxExor</span><span>(</span><span>int</span> <span>num</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>int</span> <span>maxNumber</span> <span>=</span> <span>0</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span> <span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)</span> <span>&</span><span>1</span><span>;</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>)){</span><span>// since we have to find opposite of bit at index i to get the max exor</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>// if we don't have reverse bit we have to settle for what we have</span> <span>}</span> <span>else</span><span>{</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>);</span> <span>maxNumber</span> <span>=</span> <span>maxNumber</span> <span>|</span> <span>1</span><span><<</span><span>i</span><span>;</span> <span>// this will add the bit at ith index in the maxNumber</span> <span>}</span> <span>}</span> <span>return</span> <span>maxNumber</span><span>;</span> <span>}</span> <span>}</span>// 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:
<span>//tc :O(n*m) : where n is length of the queries list, and m is the size of the arr list</span><span>import</span> <span>java.util.*</span><span>;</span><span>public</span> <span>class</span> <span>Solution</span> <span>{</span><span>public</span> <span>static</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>maxXorQueries</span><span>(</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr</span><span>,</span> <span>ArrayList</span><span><</span><span>ArrayList</span><span><</span><span>Integer</span><span>>></span> <span>queries</span><span>)</span> <span>{</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>result</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span><span>for</span><span>(</span> <span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span><span>int</span> <span>X</span> <span>=</span> <span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>0</span><span>);</span><span>int</span> <span>A</span> <span>=</span> <span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>1</span><span>);</span><span>int</span> <span>max</span> <span>=</span> <span>-</span><span>1</span><span>;</span><span>for</span><span>(</span><span>Integer</span> <span>j</span> <span>:</span> <span>arr</span><span>){</span><span>if</span><span>(</span><span>j</span><span><=</span><span>A</span><span>){</span><span>max</span> <span>=</span> <span>Integer</span><span>.</span><span>max</span><span>(</span><span>max</span><span>,</span><span>X</span><span>^</span><span>j</span><span>);</span><span>}</span><span>}</span><span>result</span><span>.</span><span>add</span><span>(</span><span>max</span><span>);</span><span>}</span><span>return</span> <span>result</span><span>;</span><span>}</span><span>}</span><span>//tc :O(n*m) : where n is length of the queries list, and m is the size of the arr list</span> <span>import</span> <span>java.util.*</span><span>;</span> <span>public</span> <span>class</span> <span>Solution</span> <span>{</span> <span>public</span> <span>static</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>maxXorQueries</span><span>(</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr</span><span>,</span> <span>ArrayList</span><span><</span><span>ArrayList</span><span><</span><span>Integer</span><span>>></span> <span>queries</span><span>)</span> <span>{</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>result</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span> <span>for</span><span>(</span> <span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span> <span>int</span> <span>X</span> <span>=</span> <span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>0</span><span>);</span> <span>int</span> <span>A</span> <span>=</span> <span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>1</span><span>);</span> <span>int</span> <span>max</span> <span>=</span> <span>-</span><span>1</span><span>;</span> <span>for</span><span>(</span><span>Integer</span> <span>j</span> <span>:</span> <span>arr</span><span>){</span> <span>if</span><span>(</span><span>j</span><span><=</span><span>A</span><span>){</span> <span>max</span> <span>=</span> <span>Integer</span><span>.</span><span>max</span><span>(</span><span>max</span><span>,</span><span>X</span><span>^</span><span>j</span><span>);</span> <span>}</span> <span>}</span> <span>result</span><span>.</span><span>add</span><span>(</span><span>max</span><span>);</span> <span>}</span> <span>return</span> <span>result</span><span>;</span> <span>}</span> <span>}</span>//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:
<span>import</span> <span>java.util.*</span><span>;</span><span>class</span> <span>QueryDetails</span><span>{</span><span>int</span> <span>xi</span><span>;</span><span>int</span> <span>ai</span><span>;</span><span>int</span> <span>index</span><span>;</span><span>public</span> <span>QueryDetails</span><span>(</span><span>int</span> <span>x</span> <span>,</span><span>int</span> <span>a</span><span>,</span> <span>int</span> <span>i</span><span>){</span><span>this</span><span>.</span><span>xi</span> <span>=</span> <span>x</span><span>;</span><span>this</span><span>.</span><span>ai</span> <span>=</span> <span>a</span><span>;</span><span>this</span><span>.</span><span>index</span> <span>=</span> <span>i</span><span>;</span><span>}</span><span>public</span> <span>int</span> <span>getX</span><span>(){</span><span>return</span> <span>xi</span><span>;</span><span>}</span><span>public</span> <span>int</span> <span>getA</span><span>(){</span><span>return</span> <span>ai</span><span>;</span><span>}</span><span>public</span> <span>int</span> <span>getIndex</span><span>(){</span><span>return</span> <span>index</span><span>;</span><span>}</span><span>}</span><span>public</span> <span>class</span> <span>Solution</span> <span>{</span><span>public</span> <span>static</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>maxXorQueries</span><span>(</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr</span><span>,</span> <span>ArrayList</span><span><</span><span>ArrayList</span><span><</span><span>Integer</span><span>>></span> <span>queries</span><span>)</span> <span>{</span><span>// Write your code here.</span><span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span><span>Collections</span><span>.</span><span>sort</span><span>(</span><span>arr</span><span>);</span><span>PriorityQueue</span><span><</span><span>QueryDetails</span><span>></span> <span>q</span> <span>=</span> <span>new</span> <span>PriorityQueue</span><span><>((</span><span>a</span><span>,</span><span>b</span><span>)-></span> <span>a</span><span>.</span><span>getA</span><span>()-</span><span>b</span><span>.</span><span>getA</span><span>());</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span><span>q</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>QueryDetails</span><span>(</span><span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>0</span><span>),</span><span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>1</span><span>),</span><span>i</span><span>));</span><span>}</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span><span>list</span><span>.</span><span>add</span><span>(-</span><span>1</span><span>);</span> <span>//intialization;// that is bound to change later</span><span>}</span><span>int</span> <span>indexOfArr</span> <span>=</span><span>0</span><span>;</span><span>while</span><span>(!</span><span>q</span><span>.</span><span>isEmpty</span><span>()){</span><span>QueryDetails</span> <span>query</span> <span>=</span> <span>q</span><span>.</span><span>remove</span><span>();</span><span>int</span> <span>x</span> <span>=</span> <span>query</span><span>.</span><span>getX</span><span>();</span><span>int</span> <span>a</span> <span>=</span> <span>query</span><span>.</span><span>getA</span><span>();</span><span>int</span> <span>index</span> <span>=</span> <span>query</span><span>.</span><span>getIndex</span><span>();</span><span>int</span> <span>max</span> <span>=</span> <span>-</span><span>1</span><span>;</span><span>while</span><span>(</span><span>indexOfArr</span><span><</span><span>arr</span><span>.</span><span>size</span><span>()</span> <span>&&</span> <span>arr</span><span>.</span><span>get</span><span>(</span><span>indexOfArr</span><span>)<=</span><span>a</span><span>){</span><span>trie</span><span>.</span><span>insert</span><span>(</span><span>arr</span><span>.</span><span>get</span><span>(</span><span>indexOfArr</span><span>));</span><span>indexOfArr</span><span>++;</span><span>}</span><span>//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 )</span><span>if</span><span>(</span><span>indexOfArr</span><span>==</span><span>0</span><span>)</span> <span>list</span><span>.</span><span>set</span><span>(</span><span>index</span><span>,</span> <span>-</span><span>1</span><span>);</span><span>else</span><span>{</span><span>max</span> <span>=</span> <span>trie</span><span>.</span><span>getMaxExor</span><span>(</span><span>x</span><span>);</span><span>list</span><span>.</span><span>set</span><span>(</span><span>index</span><span>,</span><span>max</span><span>);</span><span>}</span><span>}</span><span>return</span> <span>list</span><span>;</span><span>}</span><span>}</span><span>class</span> <span>Node</span><span>{</span><span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>2</span><span>];</span><span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>int</span> <span>bit</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>bit</span><span>]!=</span><span>null</span><span>;</span><span>}</span><span>public</span> <span>void</span> <span>put</span><span>(</span><span>int</span> <span>bit</span><span>,</span> <span>Node</span> <span>n</span><span>){</span><span>node</span><span>[</span><span>bit</span><span>]</span> <span>=</span> <span>n</span><span>;</span><span>}</span><span>public</span> <span>Node</span> <span>get</span><span>(</span><span>int</span> <span>bit</span><span>){</span><span>return</span> <span>node</span><span>[</span><span>bit</span><span>];</span><span>}</span><span>}</span><span>class</span> <span>Trie</span><span>{</span><span>Node</span> <span>root</span><span>;</span><span>public</span> <span>Trie</span><span>(){</span><span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span><span>}</span><span>public</span> <span>void</span> <span>insert</span><span>(</span><span>int</span> <span>num</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span><span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)&</span><span>1</span><span>;</span><span>// this will check if the bit at index i</span><span>//is set or not (basically this helps putting the num bits in</span><span>//the trie from right bit to left bit)</span><span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>bit</span><span>)){</span><span>node</span><span>.</span><span>put</span><span>(</span><span>bit</span><span>,</span><span>new</span> <span>Node</span><span>());</span><span>}</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>}</span><span>}</span><span>public</span> <span>int</span> <span>getMaxExor</span><span>(</span><span>int</span> <span>num</span><span>){</span><span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span><span>int</span> <span>maxNumber</span> <span>=</span> <span>0</span> <span>;</span><span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span><span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)</span> <span>&</span><span>1</span><span>;</span><span>if</span><span>(</span><span>node</span><span>!=</span><span>null</span> <span>&&</span> <span>!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>)){</span><span>// since we have to find opposite of bit at index i to get the max exor</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>// if we don't have reverse bit we have to settle for what we have</span><span>}</span><span>else</span><span>{</span><span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>);</span><span>maxNumber</span> <span>=</span> <span>maxNumber</span> <span>|</span> <span>1</span><span><<</span><span>i</span><span>;</span> <span>// this will add the bit at ith index in the maxNumber</span><span>}</span><span>}</span><span>return</span> <span>maxNumber</span><span>;</span><span>}</span><span>}</span><span>import</span> <span>java.util.*</span><span>;</span> <span>class</span> <span>QueryDetails</span><span>{</span> <span>int</span> <span>xi</span><span>;</span> <span>int</span> <span>ai</span><span>;</span> <span>int</span> <span>index</span><span>;</span> <span>public</span> <span>QueryDetails</span><span>(</span><span>int</span> <span>x</span> <span>,</span><span>int</span> <span>a</span><span>,</span> <span>int</span> <span>i</span><span>){</span> <span>this</span><span>.</span><span>xi</span> <span>=</span> <span>x</span><span>;</span> <span>this</span><span>.</span><span>ai</span> <span>=</span> <span>a</span><span>;</span> <span>this</span><span>.</span><span>index</span> <span>=</span> <span>i</span><span>;</span> <span>}</span> <span>public</span> <span>int</span> <span>getX</span><span>(){</span> <span>return</span> <span>xi</span><span>;</span> <span>}</span> <span>public</span> <span>int</span> <span>getA</span><span>(){</span> <span>return</span> <span>ai</span><span>;</span> <span>}</span> <span>public</span> <span>int</span> <span>getIndex</span><span>(){</span> <span>return</span> <span>index</span><span>;</span> <span>}</span> <span>}</span> <span>public</span> <span>class</span> <span>Solution</span> <span>{</span> <span>public</span> <span>static</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>maxXorQueries</span><span>(</span><span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>arr</span><span>,</span> <span>ArrayList</span><span><</span><span>ArrayList</span><span><</span><span>Integer</span><span>>></span> <span>queries</span><span>)</span> <span>{</span> <span>// Write your code here.</span> <span>Trie</span> <span>trie</span> <span>=</span> <span>new</span> <span>Trie</span><span>();</span> <span>Collections</span><span>.</span><span>sort</span><span>(</span><span>arr</span><span>);</span> <span>PriorityQueue</span><span><</span><span>QueryDetails</span><span>></span> <span>q</span> <span>=</span> <span>new</span> <span>PriorityQueue</span><span><>((</span><span>a</span><span>,</span><span>b</span><span>)-></span> <span>a</span><span>.</span><span>getA</span><span>()-</span><span>b</span><span>.</span><span>getA</span><span>());</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span><span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span> <span>q</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>QueryDetails</span><span>(</span><span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>0</span><span>),</span><span>queries</span><span>.</span><span>get</span><span>(</span><span>i</span><span>).</span><span>get</span><span>(</span><span>1</span><span>),</span><span>i</span><span>));</span> <span>}</span> <span>ArrayList</span><span><</span><span>Integer</span><span>></span> <span>list</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>0</span><span>;</span><span>i</span><span><</span> <span>queries</span><span>.</span><span>size</span><span>();</span><span>i</span><span>++){</span> <span>list</span><span>.</span><span>add</span><span>(-</span><span>1</span><span>);</span> <span>//intialization;// that is bound to change later</span> <span>}</span> <span>int</span> <span>indexOfArr</span> <span>=</span><span>0</span><span>;</span> <span>while</span><span>(!</span><span>q</span><span>.</span><span>isEmpty</span><span>()){</span> <span>QueryDetails</span> <span>query</span> <span>=</span> <span>q</span><span>.</span><span>remove</span><span>();</span> <span>int</span> <span>x</span> <span>=</span> <span>query</span><span>.</span><span>getX</span><span>();</span> <span>int</span> <span>a</span> <span>=</span> <span>query</span><span>.</span><span>getA</span><span>();</span> <span>int</span> <span>index</span> <span>=</span> <span>query</span><span>.</span><span>getIndex</span><span>();</span> <span>int</span> <span>max</span> <span>=</span> <span>-</span><span>1</span><span>;</span> <span>while</span><span>(</span><span>indexOfArr</span><span><</span><span>arr</span><span>.</span><span>size</span><span>()</span> <span>&&</span> <span>arr</span><span>.</span><span>get</span><span>(</span><span>indexOfArr</span><span>)<=</span><span>a</span><span>){</span> <span>trie</span><span>.</span><span>insert</span><span>(</span><span>arr</span><span>.</span><span>get</span><span>(</span><span>indexOfArr</span><span>));</span> <span>indexOfArr</span><span>++;</span> <span>}</span> <span>//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 )</span> <span>if</span><span>(</span><span>indexOfArr</span><span>==</span><span>0</span><span>)</span> <span>list</span><span>.</span><span>set</span><span>(</span><span>index</span><span>,</span> <span>-</span><span>1</span><span>);</span> <span>else</span><span>{</span> <span>max</span> <span>=</span> <span>trie</span><span>.</span><span>getMaxExor</span><span>(</span><span>x</span><span>);</span> <span>list</span><span>.</span><span>set</span><span>(</span><span>index</span><span>,</span><span>max</span><span>);</span> <span>}</span> <span>}</span> <span>return</span> <span>list</span><span>;</span> <span>}</span> <span>}</span> <span>class</span> <span>Node</span><span>{</span> <span>Node</span> <span>node</span><span>[]</span> <span>=</span> <span>new</span> <span>Node</span><span>[</span><span>2</span><span>];</span> <span>public</span> <span>boolean</span> <span>containsKey</span><span>(</span><span>int</span> <span>bit</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>bit</span><span>]!=</span><span>null</span><span>;</span> <span>}</span> <span>public</span> <span>void</span> <span>put</span><span>(</span><span>int</span> <span>bit</span><span>,</span> <span>Node</span> <span>n</span><span>){</span> <span>node</span><span>[</span><span>bit</span><span>]</span> <span>=</span> <span>n</span><span>;</span> <span>}</span> <span>public</span> <span>Node</span> <span>get</span><span>(</span><span>int</span> <span>bit</span><span>){</span> <span>return</span> <span>node</span><span>[</span><span>bit</span><span>];</span> <span>}</span> <span>}</span> <span>class</span> <span>Trie</span><span>{</span> <span>Node</span> <span>root</span><span>;</span> <span>public</span> <span>Trie</span><span>(){</span> <span>root</span> <span>=</span> <span>new</span> <span>Node</span><span>();</span> <span>}</span> <span>public</span> <span>void</span> <span>insert</span><span>(</span><span>int</span> <span>num</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span> <span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span> <span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)&</span><span>1</span><span>;</span><span>// this will check if the bit at index i</span> <span>//is set or not (basically this helps putting the num bits in</span> <span>//the trie from right bit to left bit)</span> <span>if</span><span>(!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>bit</span><span>)){</span> <span>node</span><span>.</span><span>put</span><span>(</span><span>bit</span><span>,</span><span>new</span> <span>Node</span><span>());</span> <span>}</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span> <span>}</span> <span>}</span> <span>public</span> <span>int</span> <span>getMaxExor</span><span>(</span><span>int</span> <span>num</span><span>){</span> <span>Node</span> <span>node</span> <span>=</span> <span>root</span><span>;</span> <span>int</span> <span>maxNumber</span> <span>=</span> <span>0</span> <span>;</span> <span>for</span><span>(</span><span>int</span> <span>i</span> <span>=</span><span>31</span><span>;</span><span>i</span><span>>=</span><span>0</span><span>;</span><span>i</span><span>--){</span> <span>int</span> <span>bit</span> <span>=</span> <span>(</span><span>num</span><span>>></span><span>i</span><span>)</span> <span>&</span><span>1</span><span>;</span> <span>if</span><span>(</span><span>node</span><span>!=</span><span>null</span> <span>&&</span> <span>!</span><span>node</span><span>.</span><span>containsKey</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>)){</span><span>// since we have to find opposite of bit at index i to get the max exor</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>bit</span><span>);</span><span>// if we don't have reverse bit we have to settle for what we have</span> <span>}</span> <span>else</span><span>{</span> <span>node</span> <span>=</span> <span>node</span><span>.</span><span>get</span><span>(</span><span>1</span><span>-</span><span>bit</span><span>);</span> <span>maxNumber</span> <span>=</span> <span>maxNumber</span> <span>|</span> <span>1</span><span><<</span><span>i</span><span>;</span> <span>// this will add the bit at ith index in the maxNumber</span> <span>}</span> <span>}</span> <span>return</span> <span>maxNumber</span><span>;</span> <span>}</span> <span>}</span>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
SDE Sheets Questions And Solutions (12 Part Series)
1 Arrays
2 Binary Tree
… 8 more parts…
3 Graph
4 String
5 Binary Search Tree
6 Greedy
7 Stack and Queue
8 DP
9 Heap(Priority Queue)
10 Recursion
11 Recursion and backtracking
12 Trie
原文链接：Trie
© 版权声明
THE END
暂无评论内容