In: Computer Science
Question: Properly convert the solution to this problem from Java to C++
Problem Statement
If you want to write a message anonymously, one way to do it is to cut out letters from headlines in a newspaper and paste them onto a blank piece of paper to form the message you want to write. Given several headlines that you have cut out, determine how many messages from a list you can write using the letters from the headlines. You should only consider each message by itself and not in conjunction with the others, see example 2.
Write the function how_many which takes as parameters a vector<string> headlines containing the headlines which you have cut out as well as a vector<string> messages with the messages you may want to write, and returns an int which is the total number of messages you can write.
Constraints
Examples
headlines = {"Earthquake in San Francisco", "Burglary at musuem in Sweden", "Poverty"} messages = {"Give me my money back", "I am the best coder", "TOPCODER"} Returns: 2
In the first message we have three 'm's, but there are only two 'm's among the headlines (both in the word "museum"), so this message can't be written.
The second message can be written. Note that the first letter, 'I', only appears as lower case in the headlines, but that's allowed. The last message can also be written, so the method should return 2.
headlines = {"Programming is fun"} messages = {"program","programmer","gaming","sing","NO FUN"} Returns: 4
The messages "program", "gaming", "sing" and "NO FUN" can all be written but not "programmer" (no 'e's exist). The method should return 4.
headlines = {"abcdef","abcdef"} messages = {"AaBbCc","aabbbcc"," ","FADE"} Returns: 3
All messages except the second one can be written, because it contains three 'b's but there are only two 'b's available. Also note the message only containing spaces - such a message can of course always be written.
Given Function
#include <vector>
#include <string>
int how_many(vector<string> headlines,
vector<string> messages) {
// fill in code here
}
Solution (Convert the Java code below to C++).
import java.util.*; public class Anonymous { public int howMany(String[] headlines, String[] messages) { HashMap<Character, Integer> lettersAvailable = countLetters(headlines); int wordsWeCanMake = 0; for(String message : messages){ String[] oneMessage = {message}; HashMap<Character, Integer> lettersNeeded = countLetters(oneMessage); boolean canMakeMessage = true; Iterator it = lettersNeeded.entrySet().iterator(); while (it.hasNext()){ Map.Entry pairs = (Map.Entry)it.next(); char key = (Character) pairs.getKey(); if(!(key==' ')){ int numNeeded = (Integer) pairs.getValue(); if(lettersAvailable.containsKey(key)){ int numAvailable = lettersAvailable.get(key); canMakeMessage = (numNeeded <= numAvailable) && canMakeMessage; } else{ canMakeMessage = false ; break; } } it.remove(); } if(canMakeMessage){ wordsWeCanMake += 1; } } return wordsWeCanMake; } public HashMap<Character, Integer> countLetters(String[] words){ HashMap<Character, Integer> counts = new HashMap<Character, Integer>(); int currentCountOfLetter = 0; for(String word : words){ for(int i=0; i<word.length(); i++){ char letter = Character.toLowerCase(word.charAt(i)); if (counts.containsKey(letter)){ currentCountOfLetter = counts.get(letter); currentCountOfLetter +=1; } else { currentCountOfLetter = 1; } counts.put(letter, currentCountOfLetter); } } return counts; } } }
Name of Proram file Anonymous.cpp
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
void countLetters(vector<string> words, map<char,int>
&counts) // I have taken the map as input parameter by
references just for the optimization purpose
{
map<char,int>:: iterator mit;
// int currentCountOfLetter = 0; no need of this variable in our
program
string s;
for(int i=0;i<words.size();i++)
{
s=words[i]; // For each string in the words vector
transform(s.begin(),s.end(),s.begin(),::tolower); // I am using
transform method decalred in algorithm header file to conver the
whole string in lower case before hand
string::iterator it;
for(it=s.begin();it!=s.end();it++) //I am iterating over strings as
it is optimized implementation and it saves time to iterate over
indexing
{
char c=*it;
mit=counts.find(c);
if(mit!=counts.end())
{
mit->second++; // increment the count of character already
present in the map by one
}
else
{
counts.insert(pair<char,int>(c,1)); // It not prersent in the
map then insert in the map with its count 1
}
}
}
}
int howMany(vector<string> headlines, vector<string>
messages)
{
char c;
vector<string> v;
int wordsWeCanMake = 0;
bool canMakeMessage;
map<char,int> lettersAvailable;
map<char,int> lettersNeeded;
string m;
map<char,int>::iterator ait;
map<char,int>::iterator nit;
countLetters(headlines,lettersAvailable);
for(int i=0;i<messages.size();i++)
{
canMakeMessage=true;
m=messages[i];
v.push_back(m);
countLetters(v,lettersNeeded);
for(nit=lettersNeeded.begin();nit!=lettersNeeded.end();nit++)
{
c = nit->first;
if(c!=' ')
{
ait = lettersAvailable.find(c);
if(ait!=lettersAvailable.end())
{
if(!(nit->second <= ait->second))
{
canMakeMessage = false;
break;
}
}
else
{
canMakeMessage = false;
break;
}
}
}
v.clear();
lettersNeeded.clear();
if(canMakeMessage)
{
wordsWeCanMake++;
}
}
return wordsWeCanMake;
}
int main() // cross verified different examples by commenting the
lines of code and it is working properly, if you want give it a
try
{
vector<string> headlines;
headlines.push_back("Earthquake in San Francisco");
headlines.push_back("Burglary at musuem in Sweden");
headlines.push_back("Poverty");
headlines.push_back("Programming is fun");
headlines.push_back("abcdef");
headlines.push_back("abcdef");
vector<string> messages;
messages.push_back("Give me my money back");
messages.push_back("I am the best coder");
messages.push_back("TOPCODER");
messages.push_back("program");
messages.push_back("programmer");
messages.push_back("gaming");
messages.push_back("sing");
messages.push_back("NO FUN");
messages.push_back("AaBbCc");
messages.push_back("aabbbcc");
messages.push_back("FADE");
cout<<howMany(headlines,messages);
return 0;
}
// Hope you are satisfied with the answer, and if you are then please rate this solution, it will be a great help.
// I have kept the variables names sames as in java code to
understand it better
// Thanks I enjoyed solving your Problem.
// If you have any confusion then please let me know in the comment
section. I will be gratefull to solve any further queries of
yours.