{"id":34208,"date":"2024-11-01T09:25:32","date_gmt":"2024-11-01T09:25:32","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34208"},"modified":"2024-11-01T10:58:10","modified_gmt":"2024-11-01T10:58:10","slug":"c-coding-test-course-dictionary","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34208\/","title":{"rendered":"C++ Coding Test Course, Dictionary"},"content":{"rendered":"
\n

Hello! Today we will tackle an algorithm problem using C++. The topic is “Dictionary Lookup”. This problem deals with the process of finding a specific word in a given list of words. We will explore the related algorithm and learn how to efficiently solve the problem.<\/p>\n

Problem Description<\/h2>\n

The problem is as follows.<\/p>\n

\n    Problem: Finding a word in a dictionary\n    - You are given a dictionary consisting of n words.\n    - When a word to search is given as input, write a program to check if this word exists in the dictionary.\n    \n    Input:\n    - The first line contains the number of words n (1 \u2264 n \u2264 100,000).\n    - In the next n lines, each line consists of a word made up of lowercase letters.\n    - The last line contains the word to search.\n    \n    Output:\n    - If the word exists in the dictionary, print 'YES', otherwise print 'NO'.\n    <\/pre>\n
Analysis of the Problem<\/h2>\n
This problem is a simple string search problem that involves finding a word in a dictionary. Therefore, the main point to solve is an efficient search method. Since the number of words can be up to 100,000, inefficient methods can lead to timeouts.<\/p>\n
The simplest method is to use a list to traverse all words and compare values, but this method has a time complexity of O(n), which is inefficient for lightweight search engines that demand optimal performance in the worst cases. Therefore, we need a method that utilizes a hashmap since it allows for average-case search time complexity of O(1).<\/p>\n
Implementation Method<\/h2>\n
Now, let’s write the code in C++ to solve the problem. We will proceed with the following steps:<\/p>\n
    \n
  1. Take the number of words as input.<\/li>\n
  2. Create a hashmap using unordered_map to store the words.<\/li>\n
  3. Add the words in the dictionary to the hashmap.<\/li>\n
  4. Input the word to search and check for its existence in the hashmap.<\/li>\n<\/ol>\n
    Code Implementation<\/h2>\n
    \n    \n    #include \n    #include \n    #include \n\n    using namespace std;\n\n    int main() {\n        int n;\n        cin >> n; \/\/ Input number of words\n        unordered_map dictionary; \/\/ Initialize the hashmap\n\n        \/\/ Input words\n        for (int i = 0; i < n; i++) {\n            string word;\n            cin >> word;\n            dictionary[word] = true; \/\/ Add word to hashmap\n        }\n\n        string searchWord;\n        cin >> searchWord; \/\/ Input the word to search\n\n        \/\/ Check the existence of the word\n        if (dictionary.find(searchWord) != dictionary.end()) {\n            cout << \"YES\" << endl; \/\/ If exists\n        } else {\n            cout << \"NO\" << endl; \/\/ If does not exist\n        }\n\n        return 0;\n    }\n    <\/code>\n    <\/pre>\n
    Code Explanation<\/h2>\n
    Let me briefly explain the code.<\/p>\n