This content originally appeared on DEV Community and was authored by Prashant Mishra
Implementing Trie data structure
Striver explanation of trie data structure
class Node{
Node [] node = new Node[26];
boolean flag;
public Node(){
}
public boolean containsKey(char c){
return node[c-'a']!=null;
}
public void put(char c, Node n){
node[c-'a'] = n;
}
public Node get(char c){
return node[c-'a'];
}
public void setFlag() {
this.flag = true;
}
public boolean getFlag(){
return this.flag;
}
}
class Trie {
Node root;
public Trie() {
root = new Node();
}
//will take tc : O(len) of the word
public void insert(String word) {
Node node = root;
for(int i =0;i<word.length();i++){
if(!node.containsKey(word.charAt(i))){
node.put(word.charAt(i),new Node());
}
node = node.get(word.charAt(i));
}
node.setFlag();
}
//will take tc : O(len) of the word
public boolean search(String word) {
Node node = root;
for(int i =0;i<word.length();i++){
if(!node.containsKey(word.charAt(i))){
return false;
}
node = node.get(word.charAt(i));
}
return node.getFlag();
}
//will take tc : O(len) of the prefix
public boolean startsWith(String prefix) {
Node node = root;
for(int i =0;i<prefix.length();i++){
if(!node.containsKey(prefix.charAt(i))){
return false;
}
node = node.get(prefix.charAt(i));
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
Trie data structure II
striver's explanation for better understanding
import java.util.* ;
import java.io.*;
class Node {
Node node[] = new Node[26];
int endWith = 0;// will keep track of no. of words ending with this word
int countPrefix=0;// will keep track of no. of words starting with this word
public Node(){
}
public boolean containsKey(char c){
return node[c-'a']!=null;
}
public void put(char c, Node n){
node[c-'a'] = n;
}
public Node get(char c){
return node[c-'a'];
}
public void incrementCountPrefix() {
++this.countPrefix;
}
public void decrementCountPrefix(){
--this.countPrefix;
}
public void incrementEndWith(){
++this.endWith;
}
public void deleteEndWith(){
--this.endWith;
}
public int getCountPrefix(){
return this.countPrefix;
}
public int getEndWith(){
return this.endWith;
}
}
public class Trie {
Node root;
public Trie() {
// Write your code here.
root = new Node();
}
public void insert(String word) {
Node node = root;
for(int i =0;i<word.length();i++){
if(!node.containsKey(word.charAt(i))){
node.put(word.charAt(i),new Node());
}
node = node.get(word.charAt(i));
node.incrementCountPrefix();
}
node.incrementEndWith();
}
public int countWordsEqualTo(String word) {
// Write your code here.
Node node = root;
for(int i=0;i<word.length();i++){
if(node.containsKey(word.charAt(i))){
node = node.get(word.charAt(i));
}
else return 0;
}
return node.getEndWith();//this will tell how many strings are
//ending with given word
}
public int countWordsStartingWith(String word) {
Node node = root;
for(int i=0;i<word.length();i++){
if(node.containsKey(word.charAt(i))){
node = node.get(word.charAt(i));
}
else return 0;
}
return node.getCountPrefix(); // it will tell how many strings are starting
//with given word;
}
public void erase(String word) {
Node node = root;
for(int i =0;i<word.length();i++){
if(node.containsKey(word.charAt(i))){
node = node.get(word.charAt(i));
node.decrementCountPrefix();
}
else return;
}
node.deleteEndWith();
}
}
Complete String
// tc : O(n*l)
import java.util.* ;
import java.io.*;
class Node{
Node[] node = new Node[26];
boolean flag;
public Node(){}
public void put(char c , Node n){
node[c-'a'] = n;
}
public boolean containsKey(char c){
return node[c-'a']!=null;
}
public Node get(char c){
return node[c-'a'];
}
public void setEnd(){
this.flag = true;
}
public boolean isEnd(){
return this.flag;
}
}
class Trie{
Node root;
public Trie(){
root = new Node();
}
public boolean checkIfPrefixPresent(String s){
Node node = root;
boolean flag= true;
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
if(!node.containsKey(c)){
return false;
}
node = node.get(c);
flag = flag && node.isEnd(); // this will check if the substring is also a string from the list of strings
//if(flag == false) return false; // this line will also work here because if any substring is not present as a string in the trie , then
// this string s won't be a complete string, and we can return false here only
}
return flag;
}
public void insert(String s){
Node node = root;
for(int i =0;i<s.length();i++){
char c = s.charAt(i);
if(!node.containsKey(c)){
node.put(c, new Node());
}
node = node.get(c);
}
node.setEnd(); // setting end of the string as this is the
//end of the current string s
}
}
class Solution {
static Node root;
public static String completeString(int n, String[] a) {
Trie trie = new Trie();
//storing all the string in the trie data structure
for(String s : a) trie.insert(s);
//finding out the comeplete string among all the list of strings
String completeString = "";
for(String s : a){
if(trie.checkIfPrefixPresent(s)){
if(completeString.length() < s.length()){
completeString = s;
}
//lexographical selection : a.compareTo(b) =-1 if a < b lexographically
else if(completeString.length() == s.length() && s.compareTo(completeString) < 0){
completeString = s;
}
}
}
return completeString.equals("") ? "None":completeString;
}
}
Count distinct substring
Tc: O(n^2) for inserting different unique substring in
Trie data structure
import java.util.ArrayList;
public class Solution
{
Node root;
static int count;
public Solution(){
root = new Node();
}
public static int countDistinctSubstrings(String s)
{
count = 0;
// Write your code here.
Solution sol = new Solution();
for(int i =0;i< s.length();i++){
String str = "";
for (int j =i;j< s.length();j++){
str = str+s.charAt(j);
sol.insert(str);
}
}
return count+1;
}
public void insert(String s){
Node node = root;
for(int i =0;i< s.length();i++){
if(!node.containsKey(s.charAt(i))){
node.put(s.charAt(i),new Node());
count++;
}
node = node.get(s.charAt(i));
}
node.setFlag();
}
}
class Node {
Node node[] = new Node[26];
boolean flag;
public Node(){
}
public boolean containsKey(char c){
return node[c-'a']!=null;
}
public Node get(char c){
return node[c-'a'];
}
public void put(char c, Node n){
node[c-'a'] = n;
}
public void setFlag(){
this.flag = true;
}
public boolean getFlag(){
return this.flag;
}
}
This content originally appeared on DEV Community and was authored by Prashant Mishra
Print
Share
Comment
Cite
Upload
Translate
Updates
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
Prashant Mishra | Sciencx (2024-07-28T16:10:46+00:00) Trie. Retrieved from https://www.scien.cx/2024/07/28/trie/
" » Trie." Prashant Mishra | Sciencx - Sunday July 28, 2024, https://www.scien.cx/2024/07/28/trie/
HARVARDPrashant Mishra | Sciencx Sunday July 28, 2024 » Trie., viewed ,<https://www.scien.cx/2024/07/28/trie/>
VANCOUVERPrashant Mishra | Sciencx - » Trie. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/07/28/trie/
CHICAGO" » Trie." Prashant Mishra | Sciencx - Accessed . https://www.scien.cx/2024/07/28/trie/
IEEE" » Trie." Prashant Mishra | Sciencx [Online]. Available: https://www.scien.cx/2024/07/28/trie/. [Accessed: ]
rf:citation » Trie | Prashant Mishra | Sciencx | https://www.scien.cx/2024/07/28/trie/ |
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.