0
\$\begingroup\$

I was asked to solve the following exercise:

Given an input vector<string>, I have to find the anagrams and return a vector<string> with only the strings that are not an anagram from other strings in the vector.

Example:

Input vector:

"code","doce","framy","frame","sad","cat","frema"

Output:

"code","framy","sad","cat"

Here, the anagram "frame" == "frema" is removed. All words which are anagrams from one another are removed.

My solution is to sum the ASCII values from the strings, if two strings are equal, then I sort it to check for equality.

#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>    // std::sort

using namespace std::chrono;
using namespace std;

int sumASCII(string input) {

    int i;
    int sum = 0;
    int size = input.size();

    for( i = 0; i < size; i++) {

        sum+=(int)input[i];
    }

    return sum;
}

int sortStringAndCompare(string &a, string &b)
{
   sort(a.begin(), a.end());
   sort(b.begin(), b.end());
   return a.compare(b);
}

vector<string> funWithAnagrams(vector<string> &text) {

    bool anagram = false;
    int i;
    int size = text.size();
    int sumCurr = 0;
    int sumPrev = 0;
    int k = 0;
    int originalSize = 0;

    string copyA;
    string copyB;

    vector<string> originalStrings;

    originalStrings.push_back(text[0]);

    for( i = 1 ; i < size;  i++ ) {
        sumCurr = sumASCII(text[i]);
        originalSize = originalStrings.size();

        for( k = 0; k < originalSize; k++ ) {


            if(originalStrings[k].size() == text[i].size() ) {
                sumPrev = sumASCII(originalStrings[k]);

                if(sumPrev == sumCurr) {// means it found a possible anagram.

                    copyA = originalStrings[k];
                    copyB = text[i];
                    if(sortStringAndCompare(copyA,copyB) == 0)
                    {
                        anagram = true;
                        break;
                    }
                }
                else
                    anagram = false;
            }
            else {
                anagram = false;
            }

        }
        if(!anagram) {
            originalStrings.push_back(text[i]);
            }
    }

    return originalStrings;
}

int stringCompare(std::string a,std::string b)
{
    return a.compare(b);

}

void print(std::vector<string> const &input)
{
    int size = input.size();
    printf("[ ");
    for (int i = 0; i < size; i++) {
        std::cout << input.at(i) << ' ';

        if(i < (size-1))
            printf(",");
    }

    printf(" ]");
}

int main() {

    printf("TEST STARTED\n");
    vector<string> input{"doceframe","code", "doce","ecod","framer","frame", "frema","cat","sad"};
    vector<string> out;

    // Get starting timepoint
    auto start = high_resolution_clock::now();
    out = funWithAnagrams(input);
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    cout << "Time taken by function: " << duration.count() << " microseconds" << endl;
    printf("\n \n");
    print(out);
    printf("\n");

    printf("TEST ENDED\n");

    return 0;

}

My program is not the best in terms of memory, i shall improve it. But my task, at the moment, is to develop the fastest algorithm possible. How can I improve it?

\$\endgroup\$
7
  • 2
    \$\begingroup\$ You could compare string lengths first, that is very fast and shows you if an anagram is even possible. \$\endgroup\$
    – Aganju
    Commented Apr 22, 2020 at 4:21
  • 3
    \$\begingroup\$ Can you clarify the behaviour? What Is "only original strings"? "code" And "doce" seem to be anagrams, So Are "frame" And "frema". But while code Is in output, frame Is not. How So? \$\endgroup\$
    – slepic
    Commented Apr 22, 2020 at 4:53
  • \$\begingroup\$ I compare strings length first with this code: if(originalStrings[k].size() == text[i].size() ) { sumPrev = sumASCII(originalStrings[k]); \$\endgroup\$ Commented Apr 22, 2020 at 9:01
  • \$\begingroup\$ What i mean by original strings is this: Consider the input "code", "doce","frame", "frema". doce is an anagram of code, so i discard doce and keep only code. Samething for frame and frema, this last word is an anagram of frame, so i discard frema. The output results: "code", "frame". Bottom line, everytime i find an anagram i discard every strings except the first one found. \$\endgroup\$ Commented Apr 22, 2020 at 9:01
  • \$\begingroup\$ You can change the sumASCII() function to use std::for_each on the input string. Doesn't matter much, but my benchmarking results showed an average reduction of 200ns in the function's running time \$\endgroup\$ Commented Apr 22, 2020 at 9:53

2 Answers 2

3
\$\begingroup\$

You are on the right track, but the code does need a lot of attention.

  1. Never go for #include <bits/stdc++.h>

    Same goes for using namespace std; Both will lead you into a lot of trouble for zero gain. Only include what you need and use proper qualifications

    #include <algorithm>
    #include <iostream>
    #include <string>
    #include <vector>
    

    Note that I also sorted the includes alphabetically so it is easy to see what is already included

  2. You should pass by value whenever it is possible. However std::string is no such case. Luckily we have std::string_view since C++17 so you should almost always prefere this to passing a std::string, e.g

    int sumASCII(const std::string_view input) {    
        int i;
        int sum = 0;
        int size = input.size();
    
        for( i = 0; i < size; i++) {
            sum+=(int)input[i];
        }
    
        return sum;
    }
    

    Same for all the other functions. Your strings are stored in the original vector so there is no possibility for a dangling reference. That said you should definitely read up on ownership and view-like types

  3. Use a formatter. Your formatting is highly unregular. You should pick a clang-format style you are comfortable with and use that everywhere.

  4. Use range-based loops when possible

    int sumASCII(const std::string_view input) {    
        int sum = 0;   
        for (const char character : input) {
            sum += (int)character;
        }    
        return sum;
    }
    
  5. Do not use C-style casts. C++ has a wide variety of specialized casts that do what they are supposed to do and not more. In the above case static_cast is sufficient

    int sumASCII(const std::string_view input) {    
        int sum = 0;   
        for (const char character : input) {
            sum += static_cast<int>(character);
        }    
        return sum;
    }
    
  6. Use the proper algorithms

    The STL provides a wide range of algorithms that is not only incredibly powerfull but also is often highly optimized and correct with respect to various corner cases.

    int sumASCII(const std::string_view input) {
        return std::accumulate(std::begin(input), std::end(input), 0);
    }
    

    Note that you might want to test this with proper warnings.

  7. Consider const correctness.

    One of the most difficult parts of programming is keeping all the moving parts in your head. The more explicit you are about what is immutable the easier it is to reason about the code. So use const whenever possible and cbegin and cend too. (Even if in this case it does exactly the same it provides additional information to the reader)

    int sumASCII(const std::string_view input) {
        return std::accumulate(std::cbegin(input), std::cend(input), 0);
    }
    
  8. Keep control flow as simple as possible.

    Another hard part of software engineering is keeping track of control flow. Try to minimize indentations as much as possible to keep the code clean and easily readable. As an example this is what you wrote

    for( i = 1 ; i < size;  i++ ) {
        sumCurr = sumASCII(text[i]);
        originalSize = originalStrings.size();
        for( k = 0; k < originalSize; k++ ) {
            if(originalStrings[k].size() == text[i].size() ) {
                sumPrev = sumASCII(originalStrings[k]);
                if(sumPrev == sumCurr) {// means it found a possible anagram.
                    copyA = originalStrings[k];
                    copyB = text[i];
                    if(sortStringAndCompare(copyA,copyB) == 0)
                    {
                        anagram = true;
                        break;
                    }
                }
                else
                    anagram = false;
            }
            else {
               anagram = false;
            }
    
        }
        if(!anagram) {
            originalStrings.push_back(text[i]);
        }
    }
    

    It is hard to keep track of the different conditions in thi loop and what it actually does so lets try to simplify it with some early returns:

    for( i = 1 ; i < size;  i++ ) {
        anagram = false;
        sumCurr = sumASCII(text[i]);
        originalSize = originalStrings.size();
        for (const string_view newString : originalStrings) {
            if(newString.size() != text[i].size() ) {
                continue;
            }
    
            sumPrev = sumASCII(newString);
            if(sumPrev != sumCurr) {
                continue;
            }
    
            copyA = originalStrings[k];
            copyB = text[i];
            if(sortStringAndCompare(copyA,copyB) == 0) {
                anagram = true;
                break;
            }
        }
    
        if(!anagram) {
            originalStrings.push_back(text[i]);
        }
    }
    

    I hope you agree that this is much easier to read.

  9. Think about the proper data structures.

    You are searching for a reoccuring pattern. This is usually done via an associative container. The STL knows std::unordered_map and std::map. You should use those.

    The first thing you need is a container of histograms,. You wantunique ones so you should go for a set

    std::unordered_set<someHistogramThing> histograms;
    

    The second thing you want to do is to count the characters in the string. Again a map is the simplest solution

    std::unordered_map<char, std::size_t> charCount;
    

    Lets have a look at how we get there;

    std::unordered_map<char, std::size_t> countCharacters(const std::string_view input) {
        std::unordered_map<char, std::size_t> charCount;
        for (const char character : input) {
            charCount[character]++;
        }
        return charCount;
    }
    

    For any word this gives us a histogram of the occurences of characters in that word. Two words are an anagram if they have the same histogram. So lets see if we can put it together.

    std::vector<std::string> removeAnagrams(const std::vector<std::string>& input) {
        std::vector<std::string> result;
        std::unordered_set<std::unordered_map<char, std::size_t>> histograms;
        for (const std::string& newWord : input) {
            const auto[it, notAnagram] = histograms.insert(countCharacters(newWord));
            if (notAnagram) {
                result.push_back(word);
            } 
        }
    }
    
  10. Usetype aliases to give your data structures better names

    using CharacterHistogram = std::unordered_map<char, std::size_t>;
    using HistogramSet = std::unordered_set<CharacterHistogram>;
    

    If we put that all together we get

    #include <string>
    #include <string_view>
    #include <vector>
    #include <unordered_map>
    #include <unordered_set>
    
    using CharacterHistogram = std::unordered_map<char, std::size_t>;
    using HistogramSet = std::unordered_set<CharacterHistogram>;
    
    CharacterHistogram countCharacters(const std::string_view input) {
        CharacterHistogram charCount;
        for (const char character : input) {
            charCount[character]++;
        }
        return charCount;
    }
    
    std::vector<std::string> removeAnagrams(const std::vector<std::string>& input) {
        std::vector<std::string> result;
        HistogramSet histograms;
        for (const std::string& newWord : input) {
            const auto[it, notAnagram] = histograms.insert(countCharacters(newWord));
            if (notAnagram) {
                result.push_back(word);
            } 
        }
    }
    
\$\endgroup\$
1
  • \$\begingroup\$ Oh thanks for the comments, i asked for quickness and got a complete rewash, i learnt so much reading your suggestions. \$\endgroup\$ Commented Apr 22, 2020 at 16:07
2
\$\begingroup\$

Your solution is O(N^2 log N) if I understand correctly.

I propose a solution that works in O(N log N):

  1. Represent each word by dictionary where the key is character and value is the count of it inside the word. Equal dictionaries will have the same count for all characters.
  2. Sort the list of dictionaries by its hash (you need to implement it) .
  3. Equal dictionaries will be adjacent to each other. So you can remove equal dictionaries in 1 pass.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.