{"id":"5ece4f65-46c1-4c0f-a50e-c5aa31d9557c","name":"Implement Trie","description":"A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings\r\n\r\nImplement the Trie class:\r\n1. Trie(): Initializes the trie object.\r\n2. void insert(String word): Inserts the string word into the trie.\r\n3. boolean search(String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.\r\n4. boolean startsWith(String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= word.length, prefix.length &lt;= 2000\r\n2. word and prefix consist only of lowercase English letters.","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n \n /** Initialize your data structure here. */\n Trie() {\n \n }\n /** Inserts a word into the trie. */\n void insert(string word) \n {\n \n }\n\n /** Returns if the word is in the trie. */\n bool search(string word) \n {\n \n }\n\n /** Returns if there is any word in the trie that starts with the given prefix. */\n\n bool startsWith(string prefix) \n {\n \n }\n};\n\nint main()\n{\n Trie *obj = new Trie();\n \n string inp;\n while (getline(cin, inp)) \n {\n vector<string> arr;\n string temp = \"\";\n for (int i=0; i<inp.size(); i++) \n {\n char s = inp[i];\n if(s== ' ' || i==inp.size()-1) \n {\n arr.push_back(temp);\n temp = \"\";\n continue;\n }\n temp.push_back(s);\n }\n if (arr[0] == \"insert\") \n obj->insert(arr[1]);\n \n else if (arr[0] == \"search\") \n cout << (obj->search(arr[1])) << endl;\n\n else if (arr[0] == \"startsWith\") \n cout << (obj->startsWith(arr[1])) << endl;\n }\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n public static class Trie {\n\n /** Initialize your data structure here. */\n public Trie() {\n\n }\n\n /** Inserts a word into the trie. */\n public void insert(String word) {\n\n }\n\n /** Returns if the word is in the trie. */\n public boolean search(String word) {\n\n }\n\n /** Returns if there is any word in the trie that starts with the given prefix. */\n public boolean startsWith(String prefix) {\n\n }\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\n\n Trie obj = new Trie();\n\n while (read.ready()) {\n String inp[] = read.readLine().split(\" \");\n\n if (inp[0].equals(\"insert\")) {\n obj.insert(inp[1]);\n } else if (inp[0].equals(\"search\")) {\n System.out.println(obj.search(inp[1]));\n } else if (inp[0].equals(\"startsWith\")) {\n System.out.println(obj.startsWith(inp[1]));\n }\n }\n\n }\n}\n"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"insert apple\r\nsearch apple\r\nsearch app\r\nstartsWith app\r\ninsert app\r\nsearch app\r\n","sampleOutput":"true\r\nfalse\r\ntrue\r\ntrue\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"48322a53-51ed-414f-9856-656592baf64e","name":"Implement Trie MCQ","slug":"implement-trie-mcq","type":0},{"id":"cb0737f7-2786-4b8d-8714-7e83cc2708dc","name":"Implement Trie","slug":"implement-trie","type":1}],"next":null,"prev":null}}

Implement Trie

A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings Implement the Trie class: 1. Trie(): Initializes the trie object. 2. void insert(String word): Inserts the string word into the trie. 3. boolean search(String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. 4. boolean startsWith(String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

{"id":"5ece4f65-46c1-4c0f-a50e-c5aa31d9557c","name":"Implement Trie","description":"A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings\r\n\r\nImplement the Trie class:\r\n1. Trie(): Initializes the trie object.\r\n2. void insert(String word): Inserts the string word into the trie.\r\n3. boolean search(String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.\r\n4. boolean startsWith(String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= word.length, prefix.length &lt;= 2000\r\n2. word and prefix consist only of lowercase English letters.","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\nusing namespace std;\n \n /** Initialize your data structure here. */\n Trie() {\n \n }\n /** Inserts a word into the trie. */\n void insert(string word) \n {\n \n }\n\n /** Returns if the word is in the trie. */\n bool search(string word) \n {\n \n }\n\n /** Returns if there is any word in the trie that starts with the given prefix. */\n\n bool startsWith(string prefix) \n {\n \n }\n};\n\nint main()\n{\n Trie *obj = new Trie();\n \n string inp;\n while (getline(cin, inp)) \n {\n vector<string> arr;\n string temp = \"\";\n for (int i=0; i<inp.size(); i++) \n {\n char s = inp[i];\n if(s== ' ' || i==inp.size()-1) \n {\n arr.push_back(temp);\n temp = \"\";\n continue;\n }\n temp.push_back(s);\n }\n if (arr[0] == \"insert\") \n obj->insert(arr[1]);\n \n else if (arr[0] == \"search\") \n cout << (obj->search(arr[1])) << endl;\n\n else if (arr[0] == \"startsWith\") \n cout << (obj->startsWith(arr[1])) << endl;\n }\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n public static class Trie {\n\n /** Initialize your data structure here. */\n public Trie() {\n\n }\n\n /** Inserts a word into the trie. */\n public void insert(String word) {\n\n }\n\n /** Returns if the word is in the trie. */\n public boolean search(String word) {\n\n }\n\n /** Returns if there is any word in the trie that starts with the given prefix. */\n public boolean startsWith(String prefix) {\n\n }\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\n\n Trie obj = new Trie();\n\n while (read.ready()) {\n String inp[] = read.readLine().split(\" \");\n\n if (inp[0].equals(\"insert\")) {\n obj.insert(inp[1]);\n } else if (inp[0].equals(\"search\")) {\n System.out.println(obj.search(inp[1]));\n } else if (inp[0].equals(\"startsWith\")) {\n System.out.println(obj.startsWith(inp[1]));\n }\n }\n\n }\n}\n"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"insert apple\r\nsearch apple\r\nsearch app\r\nstartsWith app\r\ninsert app\r\nsearch app\r\n","sampleOutput":"true\r\nfalse\r\ntrue\r\ntrue\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"4b4725b5-4896-4b68-aae2-03ea1e2ecbb2","name":"Trie For Intermediate","slug":"trie-for-intermediate-9996","type":0},{"id":"48322a53-51ed-414f-9856-656592baf64e","name":"Implement Trie MCQ","slug":"implement-trie-mcq","type":0},{"id":"cb0737f7-2786-4b8d-8714-7e83cc2708dc","name":"Implement Trie","slug":"implement-trie","type":1}],"next":null,"prev":null}}
plane

Editor

Loading...

Implement Trie

medium

A trie or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings Implement the Trie class: 1. Trie(): Initializes the trie object. 2. void insert(String word): Inserts the string word into the trie. 3. boolean search(String word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. 4. boolean startsWith(String prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Constraints

1. 1 <= word.length, prefix.length <= 2000 2. word and prefix consist only of lowercase English letters.

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

insert apple search apple search app startsWith app insert app search app

Sample Output

true false true true

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode