Recognizing anagrams Given a Vector<string> phrases, remove each phrase that is

Question

Recognizing anagrams

Given a Vector<string> phrases, remove each phrase that is an anagram of an earlier phrase, and return the remaining phrases in their original order. Do all of this in C++.

Examples:

The code in bold CANNOT be changed:

#include <algorithm>

bool isValid(string s1, string s2){
if(s1.length() == s2.length()){
for(int i = 0; i < s1.length();i++){
s2[i]=tolower(s2[i]);
s1[i]=tolower(s1[i]);
if (s2[i] == ' '){
s2[i] = '_';
}
if (s1[i] == ' '){
s1[i] = '_';
}
}
}
if(s1.length() != s2.length()){
return false;
}
std::sort(s1.begin(), s1.end());
std::sort(s2.begin(), s2.end());
bool is_valid = true;
for(int i = 0; i < s1.length();i++){
if(s1[i] != s2[i]){
is_valid = false;
}
}
return is_valid;
}

Vector<string> anagrams(Vector<string> phrases) {
Vector<string> grams;
  
for(int i = 0; i < phrases.size() - 1; i++){
for(int j = i + 1; j < phrases.size(); j++){
if(isValid(phrases[i],phrases[j])){
grams += phrases[i];
phrases.remove(j);
}
}
}
  
return grams;
}

Explanation / Answer

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool isValid(std::string s1, std::string s2){

   //Remove spaces from both the strings
   std::string::iterator end_pos = std::remove(s1.begin(), s1.end(), ' ');
   s1.erase(end_pos, s1.end());
   std::string::iterator end_pos2 = std::remove(s2.begin(), s2.end(), ' ');
   s2.erase(end_pos2, s2.end());

   if(s1.length() == s2.length()){
       //Convert all characters to lower case
       for(int i = 0; i < s1.length();i++){
           s2[i]=tolower(s2[i]);
           s1[i]=tolower(s1[i]);

       }

       //Sort the strings
       std::sort(s1.begin(), s1.end());
       std::sort(s2.begin(), s2.end());
       cout << s1 <<" " << s2<<endl;
       //Check if the two sorted strings are equal
       for(int i = 0; i < s1.length();i++){
           if(s1[i] != s2[i]){
           return false;
           }
       }
   } else {
       return false;
   }
return true;
}
vector<string> anagrams(vector<string> phrases) {
   vector<string> grams;
   // for(int i=0;i< phrases.size();i++){
   //    std::cout << phrases[i];
   // }
   if(phrases.size() == 0){
       return grams;
   } else {

       grams.push_back(phrases[0]);
       if(phrases.size() == 1){      
           return grams;
       }
       // std::cout << "looking.. ";
       for(int i = 1; i <= phrases.size() - 1; i++){
           bool is_found = false;
           for(int j = 0; j < grams.size(); j++){
               if(isValid(grams[j],phrases[i])){
                   is_found = true;
                   // cout << grams[j]<< phrases[i]<< is_found <<endl;
                   break;
               }
           }

           if(!is_found){
               grams.push_back(phrases[i]);
           }
       }
   }

  
return grams;
}
int main(){
   std::vector<std::string> phrases;
   phrases.push_back("SnapDragon vs tomek");
   phrases.push_back("savants groped mons"); // This is not equal to first one as 3 s are there in it as opposed to 2 in first string
   phrases.push_back("Adam vents prongs ok");

   // phrases.push_back("Aaagmnrs");
   // phrases.push_back("TopCoder");
   // phrases.push_back("anagrams");
   // phrases.push_back("Drop Cote");
   std::vector<std::string> grams;
   grams = anagrams(phrases);
   for(int i=0;i< grams.size();i++){
       std::cout << grams[i]<<endl;
   }  
}
// { "SnapDragon vs tomek", "savants groped monk", "Adam vents prongs ok" }
// Returns: { "SnapDragon vs tomek", "savants groped monk" }
// { "Aaagmnrs", "TopCoder", "anagrams", "Drop Cote" }
// Returns: { "Aaagmnrs", "TopCoder" }

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.