Question

In: Computer Science

Write a program (O(n), where n is the number of words) that takes as input a...

Write a program (O(n), where n is the number of words) that takes as input a set of words and returns groups of anagrams for those words. Complete your code here Do not change anything in the test file.

CPP File:

#include
#include
#include
#include

using namespace std;
vector> findAnagrams(const vector& dict);

vector> findAnagrams(const vector& dict)
{

// Your code here...


}

Test File:

#include
#include
#include
#include

using namespace std;
vector> findAnagrams(const vector& dict);

int main()
{
vector word_list = {"debitcard", "elvis", "silent", "badcredit", "lives", "freedom", "listen", "levis"};
vector> result = findAnagrams(word_list);
for (auto anagrams: result) {
for (auto words: anagrams)
cout << words << " ";
cout << endl;
}
return 0;

/* Output should be -

silent listen
debitcard badcredit
elvis lives levis

*/
}

The expected output should be in this order ONLY:

freedom

silent listen

debitcard badcredit

elvis lives levis

Solutions

Expert Solution

code snippet for the function findAnagrams:

{

// Your code here...
        vector<string>original, new_list;
        new_list.insert(new_list.end(), dict.begin(), dict.end());

        for (string &s : new_list)
                sort(s.begin(), s.end());

        unordered_map<string, vector<int>> map;
        for (int i = 0; i < dict.size(); i++)
                map[new_list[i]].push_back(i);

        vector<vector<string>> ans;

        for (auto itr : map)
        {
                vector<string>tmp;
                for (int index : itr.second)
                        tmp.push_back(dict[index]);

                ans.push_back(tmp);
        }

        return ans;

}

Complete code including driver main function to run in single file:

#include<bits/stdc++.h>
using namespace std;
vector<vector<string>> findAnagrams(const vector<string>&dict)
{

// Your code here...
        vector<string>original, new_list;
        new_list.insert(new_list.end(), dict.begin(), dict.end());

        for (string &s : new_list)
                sort(s.begin(), s.end());

        unordered_map<string, vector<int>> map;
        for (int i = 0; i < dict.size(); i++)
                map[new_list[i]].push_back(i);

        vector<vector<string>> ans;

        for (auto itr : map)
        {
                vector<string>tmp;
                for (int index : itr.second)
                        tmp.push_back(dict[index]);

                ans.push_back(tmp);
        }

        return ans;

}

int main()
{
        vector<string>word_list= {"debitcard", "elvis", "silent", "badcredit", "lives", "freedom", "listen", "levis"};
        vector<vector<string>> result = findAnagrams(word_list);
        for (auto anagrams : result) {
                for (auto words : anagrams)
                        cout << words << " ";
                cout << endl;
                
        }
        return 0;
}

EXPLANATION:

created another list and sorted each word to create a index for individual anagramic strings and after that created a map to store the index of all anagramic strings together (grouped). After that interated through the map and stored the same grouped anagramic strings together and returned the vector of vector strings.

NOTE: if any doubt or problem with the code let me know in the comment section and do upvote.


Related Solutions

Write a function in Matlab that takes as input the number n and a symmetric tridiagonal...
Write a function in Matlab that takes as input the number n and a symmetric tridiagonal matrix given as two vectors: n×1 vector v representing the main diagonal and (n−1)×1 vector w representing the upper diagonal. Have this function output the Cholesky factor of the matrix as a vector for the main diagonal and a vector for the upper diagonal and output the number of flops and, separately, the number of square roots used as well. Use only basic programming....
Write a program in C or C++ that takes a number series of size n (n...
Write a program in C or C++ that takes a number series of size n (n integers) as input from the user, push all the numbers to the stack, and reverse the stack using recursion. Please note that this is not simply popping and printing the numbers, but the program should manipulate the stack to have the numbers stored in reverse order. In addition to the provided header file, the students can use the following function to print the content...
(8%) Write a C/C++ program that takes an input (array) from 1 to n (say n...
(8%) Write a C/C++ program that takes an input (array) from 1 to n (say n = 50) and displays the string representations of those numbers with following conditions If the current number is divisible by 2, then print CSU If the current number is divisible by 5, then print SB If the current number is divisible by both 2 and 5, then print CSUSB If the number is neither divisible by 2 nor 5, then print the number Example:...
Write a program that takes its input from a file of number type double and outputs...
Write a program that takes its input from a file of number type double and outputs the average of the numbers in the file to the screen. The file contains nothing but numbers of the type double separated by blanks and/ or line breaks. If this is being done as a class assignment, obtain the file name from your instructor. File name: pr01hw05input.txt 78.0 87.5 98.1 101.0 4.3 17.2 78.0 14.5 29.6 10.2 14.2 60.7 78.3 89.3 29.1 102.3 54.1...
PART 1: WRITE A PROGRAM THAT TAKES IN TWO INTEGERS VALUE N AND M (USER INPUT)...
PART 1: WRITE A PROGRAM THAT TAKES IN TWO INTEGERS VALUE N AND M (USER INPUT) AND CALCULATES THE NTH FIBONACCI SUM USING RECURSION. EXAMPLE: OLD VERSION 0,1,1,2,3.. USING USER INPUT: 0, N, M ,N+M, (N+M)+M PART 2: WRITE THE SAME PROGRAM USING USER INPUT BUT USING A LOOP IN STEAD OF RECURSION. PYTHON
Write a C program to find out the number of words in an input text file...
Write a C program to find out the number of words in an input text file (in.txt). Also, make a copy of the input file. Solve in C programming.
Write a program that takes a date as input and outputs the date's season. The input...
Write a program that takes a date as input and outputs the date's season. The input is a string to represent the month and an int to represent the day. Ex: If the input is: April 11 the output is: Spring In addition, check if the string and int are valid (an actual month and day). Ex: If the input is: Blue 65 the output is: Invalid The dates for each season are: Spring: March 20 - June 20 Summer:...
The runtime of a program is proportional to n1.5 where n is the input size.  For input...
The runtime of a program is proportional to n1.5 where n is the input size.  For input size 100 the runtime is 51 ms.  What is the new runtime when the input size is quadrupled?
Write a function that takes a number as input, and returns the character A if the...
Write a function that takes a number as input, and returns the character A if the input is 90 and above, B if it’s 80 and above but less than 90, C if it’s at least 70 but less than 80, D if it’s at least 60 but less than 70, and F if it’s less than 60. If the input is not a number or is negative, the function should exit 1 with an error (by calling the Matlab...
Write a program to implement problem statement below: provide the menu for input N and number...
Write a program to implement problem statement below: provide the menu for input N and number of experiment M to calculate average time on M runs. randomly generated list. State your estimate on the BigO number of your algorithm/program logic. (we discussed in the class) Measure the performance of your program by given different N with randomly generated list with multiple experiment of Ns against time to draw the BigO graph (using excel) we discussed during the lecture. Lab-08-BigBiggerBiggtest.png ***...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT