{"id":"e9603832-7b06-47c7-9126-886ea8001170","name":"Design Add And Search Words Data Structure","description":"Design a data structure that supports adding new words and finding if a string matches any previously added string.\r\n\r\nImplement the WordDictionary class:\r\n1. WordDictionary() Initializes the object.\r\n2. void addWord(word) Adds word to the data structure, it can be matched later.\r\n3. boolean search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= word.length &lt;= 500\r\n2. word in addWord consists lower-case English letters.\r\n3. word in search consist of '.' or lower-case English letters.","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n\nclass WordDictionary {\n\n WordDictionary() {\n }\n\n /** Adds a word into the data structure. */\n void addWord(string word) {\n }\n\n /**\n * Returns if the word is in the data structure. A word could contain the dot\n * character '.' to represent any one letter.\n */\n bool search(string word) {\n }\n};\n\n\nint main()\n{\n WordDictionary* obj = new WordDictionary();\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] == \"addWord\")\n obj->addWord(arr[1]);\n\n else if (arr[0] == \"search\")\n cout << (obj->search(arr[1]) == true ? \"true\" : \"false\") << endl;\n }\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class WordDictionary {\r\n\r\n public WordDictionary() {\r\n }\r\n\r\n /** Adds a word into the data structure. */\r\n public void addWord(String word) {\r\n }\r\n\r\n /**\r\n * Returns if the word is in the data structure. A word could contain the dot\r\n * character ''.'' to represent any one letter.\r\n */\r\n public boolean search(String word) {\r\n }\r\n }\r\n\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n WordDictionary obj = new WordDictionary();\r\n\r\n while (read.ready()) {\r\n String inp[] = read.readLine().split(\" \");\r\n\r\n if (inp[0].equals(\"addWord\")) {\r\n obj.addWord(inp[1]);\r\n } else if (inp[0].equals(\"search\")) {\r\n System.out.println(obj.search(inp[1]));\r\n }\r\n }\r\n\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"addWord bad\r\naddWord dad\r\naddWord mad\r\nsearch pad\r\nsearch bad\r\nsearch .ad\r\nsearch b..\r\n","sampleOutput":"false\r\ntrue\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":"6044118a-9254-4d11-ac01-91eb0793ad4d","name":"Design Add And Search Words Data Structure MCQ","slug":"design-add-and-search-words-data-structure-mcq","type":0},{"id":"a2b14ec2-e10c-4574-8811-27684da98521","name":"Design Add And Search Words Data Structure","slug":"design-add-and-search-words-data-structure","type":1}],"next":null,"prev":null}}

Design Add And Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: 1. WordDictionary() Initializes the object. 2. void addWord(word) Adds word to the data structure, it can be matched later. 3. boolean search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

{"id":"e9603832-7b06-47c7-9126-886ea8001170","name":"Design Add And Search Words Data Structure","description":"Design a data structure that supports adding new words and finding if a string matches any previously added string.\r\n\r\nImplement the WordDictionary class:\r\n1. WordDictionary() Initializes the object.\r\n2. void addWord(word) Adds word to the data structure, it can be matched later.\r\n3. boolean search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.\r\n","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. 1 &lt;= word.length &lt;= 500\r\n2. word in addWord consists lower-case English letters.\r\n3. word in search consist of '.' or lower-case English letters.","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n\nusing namespace std;\n\nclass WordDictionary {\n\n WordDictionary() {\n }\n\n /** Adds a word into the data structure. */\n void addWord(string word) {\n }\n\n /**\n * Returns if the word is in the data structure. A word could contain the dot\n * character '.' to represent any one letter.\n */\n bool search(string word) {\n }\n};\n\n\nint main()\n{\n WordDictionary* obj = new WordDictionary();\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] == \"addWord\")\n obj->addWord(arr[1]);\n\n else if (arr[0] == \"search\")\n cout << (obj->search(arr[1]) == true ? \"true\" : \"false\") << endl;\n }\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class WordDictionary {\r\n\r\n public WordDictionary() {\r\n }\r\n\r\n /** Adds a word into the data structure. */\r\n public void addWord(String word) {\r\n }\r\n\r\n /**\r\n * Returns if the word is in the data structure. A word could contain the dot\r\n * character ''.'' to represent any one letter.\r\n */\r\n public boolean search(String word) {\r\n }\r\n }\r\n\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n WordDictionary obj = new WordDictionary();\r\n\r\n while (read.ready()) {\r\n String inp[] = read.readLine().split(\" \");\r\n\r\n if (inp[0].equals(\"addWord\")) {\r\n obj.addWord(inp[1]);\r\n } else if (inp[0].equals(\"search\")) {\r\n System.out.println(obj.search(inp[1]));\r\n }\r\n }\r\n\r\n }\r\n}\r\n"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"addWord bad\r\naddWord dad\r\naddWord mad\r\nsearch pad\r\nsearch bad\r\nsearch .ad\r\nsearch b..\r\n","sampleOutput":"false\r\ntrue\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":"6044118a-9254-4d11-ac01-91eb0793ad4d","name":"Design Add And Search Words Data Structure MCQ","slug":"design-add-and-search-words-data-structure-mcq","type":0},{"id":"a2b14ec2-e10c-4574-8811-27684da98521","name":"Design Add And Search Words Data Structure","slug":"design-add-and-search-words-data-structure","type":1}],"next":null,"prev":null}}
plane

Editor

Loading...

Design Add And Search Words Data Structure

medium

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: 1. WordDictionary() Initializes the object. 2. void addWord(word) Adds word to the data structure, it can be matched later. 3. boolean search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Constraints

1. 1 <= word.length <= 500 2. word in addWord consists lower-case English letters. 3. word in search consist of '.' or lower-case English letters.

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

addWord bad addWord dad addWord mad search pad search bad search .ad search b..

Sample Output

false true true true

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode