Trie में Insert और Search

#include <iostream>
#include <unordered_map>
using namespace std;
struct Node { unordered_map<char,Node*> children; bool isEnd=false; };
Node* root = new Node();
void insert(string word) {
	Node* cur = root;
	for (char c : word) {
		if (!cur->children.count(c)) cur->children[c] = new Node();
		cur = cur->children[c];
	}
	cur->isEnd = true;
}
int main() { insert("cat"); cout << "'cat' inserted, new node created for each missing character link"; return 0; }

import java.util.*;
public class Main {
	static class Node { Map<Character,Node> children = new HashMap<>(); boolean isEnd = false; }
	static Node root = new Node();
	static void insert(String word) {
		Node cur = root;
		for (char c : word.toCharArray()) {
			cur.children.putIfAbsent(c, new Node());
			cur = cur.children.get(c);
		}
		cur.isEnd = true;
	}
	public static void main(String[] args) {
		insert("cat");
		System.out.println("'cat' inserted, new node created for each missing character link");
	}
}

class Node:
    def __init__(self):
        self.children = {}
        self.is_end = False
root = Node()
def insert(word):
    cur = root
    for ch in word:
        if ch not in cur.children:
            cur.children[ch] = Node()
        cur = cur.children[ch]
    cur.is_end = True
insert("cat")
print("'cat' inserted, new node created for each missing character link")

#include <stdio.h>
struct Node { struct Node* children[26]; int isEnd; };
struct Node nodes[100]; int nodeCount = 1;
void insert(char* word) {
	int cur = 0;
	for (int i = 0; word[i]; i++) {
		int idx = word[i]-'a';
		if (!nodes[cur].children[idx]) { nodes[cur].children[idx] = &nodes[nodeCount]; nodeCount++; }
	}
}
int main() {
	insert("cat");
	printf("'cat' inserted, new node created for each missing character link");
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
#include <unordered_map>
using namespace std;
struct Node { unordered_map<char,Node*> children; bool isEnd=false; };
Node* root = new Node();
bool search(string word) {
	Node* cur = root;
	for (char c : word) {
		if (!cur->children.count(c)) return false;
		cur = cur->children[c];
	}
	return cur->isEnd;
}
int main() { cout << (search("cat") ? "found" : "not found, missing link or isEnd not set"); return 0; }

import java.util.*;
public class Main {
	static class Node { Map<Character,Node> children = new HashMap<>(); boolean isEnd = false; }
	static Node root = new Node();
	static boolean search(String word) {
		Node cur = root;
		for (char c : word.toCharArray()) {
			if (!cur.children.containsKey(c)) return false;
			cur = cur.children.get(c);
		}
		return cur.isEnd;
	}
	public static void main(String[] args) {
		System.out.println(search("cat") ? "found" : "not found, missing link or isEnd not set");
	}
}

class Node:
    def __init__(self):
        self.children = {}
        self.is_end = False
root = Node()
def search(word):
    cur = root
    for ch in word:
        if ch not in cur.children:
            return False
        cur = cur.children[ch]
    return cur.is_end
print("found" if search("cat") else "not found, missing link or is_end not set")

#include <stdio.h>
struct Node { struct Node* children[26]; int isEnd; };
struct Node nodes[100]; int nodeCount = 1;
int search(char* word) {
	int cur = 0;
	for (int i = 0; word[i]; i++) {
		int idx = word[i]-'a';
		if (!nodes[cur].children[idx]) return 0;
	}
	return nodes[cur].isEnd;
}
int main() { printf(search("cat") ? "found" : "not found, missing link or isEnd not set"); return 0; }

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	bool prefixCa_reachable = true, prefixCa_isWord = false;
	cout << "'ca' reachable=" << prefixCa_reachable << " but never inserted as a full word, isEnd=" << prefixCa_isWord;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		boolean prefixReachable = true, prefixIsWord = false;
		System.out.println("'ca' reachable=" + prefixReachable + " but never inserted as a full word, isEnd=" + prefixIsWord);
	}
}

prefix_reachable, prefix_is_word = True, False
print(f"'ca' reachable={prefix_reachable} but never inserted as a full word, is_end={prefix_is_word}")

#include <stdio.h>
int main() {
	int prefixReachable = 1, prefixIsWord = 0;
	printf("'ca' reachable=%d but never inserted as a full word, isEnd=%d", prefixReachable, prefixIsWord);
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	cout << "Insert and search: O(L) where L = word length, independent of how many other words are stored";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Insert and search: O(L) where L = word length, independent of how many other words are stored");
	}
}

print("Insert and search: O(L) where L = word length, independent of how many other words are stored")

#include <stdio.h>
int main() {
	printf("Insert and search: O(L) where L = word length, independent of how many other words are stored");
	return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
	cout << "Autocomplete: walk to a prefix's node, then explore everything beneath it";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Autocomplete: walk to a prefix's node, then explore everything beneath it");
	}
}

print("Autocomplete: walk to a prefix's node, then explore everything beneath it")

#include <stdio.h>
int main() {
	printf("Autocomplete: walk to a prefix's node, then explore everything beneath it");
	return 0;
}

Login to try C/C++/Java code in the editor