C++ Coding Test Course, Dictionary

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.

Problem Description

The problem is as follows.

    Problem: Finding a word in a dictionary
    - You are given a dictionary consisting of n words.
    - When a word to search is given as input, write a program to check if this word exists in the dictionary.
    
    Input:
    - The first line contains the number of words n (1 ≤ n ≤ 100,000).
    - In the next n lines, each line consists of a word made up of lowercase letters.
    - The last line contains the word to search.
    
    Output:
    - If the word exists in the dictionary, print 'YES', otherwise print 'NO'.

Analysis of the Problem

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.

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).

Implementation Method

Now, let’s write the code in C++ to solve the problem. We will proceed with the following steps:

  1. Take the number of words as input.
  2. Create a hashmap using unordered_map to store the words.
  3. Add the words in the dictionary to the hashmap.
  4. Input the word to search and check for its existence in the hashmap.

Code Implementation

    
    #include 
    #include 
    #include 

    using namespace std;

    int main() {
        int n;
        cin >> n; // Input number of words
        unordered_map dictionary; // Initialize the hashmap

        // Input words
        for (int i = 0; i < n; i++) {
            string word;
            cin >> word;
            dictionary[word] = true; // Add word to hashmap
        }

        string searchWord;
        cin >> searchWord; // Input the word to search

        // Check the existence of the word
        if (dictionary.find(searchWord) != dictionary.end()) {
            cout << "YES" << endl; // If exists
        } else {
            cout << "NO" << endl; // If does not exist
        }

        return 0;
    }

Code Explanation

Let me briefly explain the code.

  • #include : Includes the library for input and output in C++.
  • #include : Library for using hashmaps, allowing for O(1) search time complexity.
  • #include : Library for handling strings.
  • unordered_map dictionary;: Declares a hashmap to store words.
  • cin >> n;: Takes the number of words as input.
  • dictionary[word] = true;: Adds the input word to the hashmap. The key of the hashmap is the word, and the value is set to true.
  • dictionary.find(searchWord): Searches for the query in the hashmap to check its existence.

Testing and Results

Now let's test this code in practice. For example, we will input the following:

    5
    apple
    banana
    cherry
    date
    elderberry
    banana

If we input as above, the output will be:

    YES

We can consider another example:

    5
    apple
    banana
    cherry
    date
    elderberry
    fig

In this case, the output will be:

    NO

Complexity Analysis

The time complexity of this algorithm is as follows:

  • Word Insertion: O(1) (on average, due to the nature of the hashmap)
  • Word Search: O(1) (also on average)

Thus, the overall time complexity is O(n). The space complexity depends on the number of words stored in the hashmap, which is O(n).

Conclusion

Today we learned how to solve the problem of finding a word in a dictionary using C++. We demonstrated how the approach using hashmaps can significantly improve time complexity. Algorithm problems can always be approached in various ways, so I encourage you to try out different methods!