[Solved] Write an algorithm to identify which words will be saved in the dictionary

write an algorithm to identify which words will be saved in the dictionary.

input: string input

output: print space-separated strings in the lexicographically sorted order representing the number of repeated words detected in the input text and if no word is repeated print “NA”.

note: A word is an alphabetically sorted sequence of characters having no spaces in between and there is no punctuation mark in the input text.

Input: cat human latt matter cat matter cat

Output: cat matter

Solution

This algorithm follows the following approach:

1. Split the input string into individual words: The algorithm iterates through each character in the input string and checks if it is a space. If it is a space, the current word is added to a map that keeps track of the number of times each word appears in the input text. If it is not a space, the character is added to the current word.
2. Count the number of times each word appears: Once all the characters have been processed, the map is iterated through and the number of times each word appears is recorded.
3. Collect words that appear more than once: Any words that appear more than once are added to a vector.
4. Sort the words lexicographically: The vector is then sorted lexicographically
5. Return the vector: The final vector is returned and in the main function, it will check if the result vector is empty or not if it is empty it will print “NA” else it will print the result in the format specified.

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

vector<string> dictWords (string textInput)
{
    vector<string>  answer;
    unordered_map<string, int> wordCount;

    // split the input string into words
    string word = "";
    for (char c : textInput) {
        if (c == ' ') {
            if (word != "") {
                wordCount[word]++;
                word = "";

                // sauravhathi
            }
        } else {
            word += c;
        }
    }
    if (word != "") {
        wordCount[word]++;
    }

    // collect words that appear more than once
    for (auto const& [key, value] : wordCount) {
        if (value > 1) {
            answer.push_back(key);
        }
    }

    // sort the words lexicographically
    sort(answer.begin(), answer.end());

    return answer;
}

int main()
{
    // input for textInput
    string textInput;
    getline(cin, textInput);

    // output
    vector<string> result = dictWords(textInput);
    if (result.empty()) {
        cout << "NA";
    } else {
        for (int idx = 0; idx < result.size() - 1; idx++) {
            cout << result[idx] << " ";
        }
        cout << result[result.size() - 1];
    }

    return 0;
}

Happy Learning – If you require any further information, feel free to contact me.