1
\$\begingroup\$

My approach for checking anagrams is:

step 1: Remove all the space from both input strings.

step 2: Sort both of the strings.

step 3: Return false if the lengths differ.

step 4 : Return true if all char matches.

#include<iostream>
#include<set>
#include<string>
#include <algorithm>

bool anagrams(std::string usr1,std::string usr2)
{
        if(usr1.length()==usr2.length())
        {

                for(std::string::size_type pos = 0 ; pos<= usr1.length()-1 ; ++pos)
                {
                        if(pos==usr1.size()-1)
                        {
                                if(usr1[pos]==usr2[pos])
                                return true;
                        }

                        if(usr1[pos]==usr2[pos])
                        {
                                continue ;
                        }
                }

        }
        return false;
}

int main()
{
        std::string userInput1;
        std::string userInput2;


        std::getline(std::cin,userInput1);
        std::getline(std::cin,userInput2);

        std::string::iterator end_pos1 = std::remove(userInput1.begin(),userInput1.end(),' ');
        userInput2.erase(end_pos1,userInput1.end());

        std::string::iterator end_pos2 = std::remove(userInput2.begin(),userInput2.end(),' ');
        userInput1.erase(end_pos2,userInput2.end());

        std::sort(userInput1.begin(),userInput1.end());
        std::sort(userInput2.begin(),userInput2.end());

        if(userInput1.empty() || userInput2.empty())
                return 0;
        if(anagrams(userInput1,userInput2))
                std::cout<<"String is anagrams"<<"\n";
        else
                std::cout<<"String  not  anagrams"<<"\n";

        return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I think, if memory consumption is not an issue, then for each string you create a hashtable/map/dictionary where the keys are letters, and the value is count of that letter in the string. If for each letter counters match in both hashtables, the strings are anagrams. \$\endgroup\$ – Igor Soloydenko Dec 8 '17 at 19:50
  • \$\begingroup\$ @IgorSoloydenko You have to be an a very small micro controller for a set of 256 integers to be an issue. Possible but rare. \$\endgroup\$ – Martin York Dec 9 '17 at 13:28
  • \$\begingroup\$ Your code in anagrams() doesn't work. It says two strings are equal the first string's last character matches the second string's last character. That is, it reports two strings as anagrams if the highest-value letter of them is the same. \$\endgroup\$ – Snowbody Dec 9 '17 at 22:52
6
\$\begingroup\$
  • anagram seems like a misnomer. A better name for such function would be is_anagram.

  • I don't see why <set> is included.

  • Fail early:

    if (usr1.length() != usr2.length()) {
        return false;
    }
    

    spares you a level of indentation.

  • Test for pos==usr1.size()-1 is waste of time, because it fails at every iteration except the last one, and still tests for characters at pos.

  • Sorting inputs is an essential part of the algorithm, and hence shall be performed inside anagram. As written, anagram only tests two string for being identical.

  • On the other hand, removing spaces does not belong to the core algorithm, and you correctly let the caller do it. You may also want to remove punctuation, and maybe convert the strings to the lower case. This logic indeed belongs to a caller.

  • Since you already #include <algorithm>, an std::equal(usr1.begin(), usr1.end(), usr2.begin()) looks more C++ish (if you are open to C++14, a variant std::equal(usr1.begin(), usr1.end(), usr2.begin(), usr2.end()) even spares the test for equal length).

All that said,

    bool is_anagram(std::string s1, std::string s2)
    {
        std::sort(s1.begin(), s1.end());
        std::sort(s2.begin(), s2.end());
        return std::equal(s1.begin(), s1.end(), s2.begin(), s2.end());
    }

As mentioned in comments, an alternative implementation using histograms is very appealing.

\$\endgroup\$
  • \$\begingroup\$ Aren't names beginning with is reserved for future standards? Or is that just in c rather than c++? \$\endgroup\$ – Toby Speight Dec 22 '17 at 12:43
  • \$\begingroup\$ @TobySpeight Chapter and verse please? If they really are, the Standard Committee may face some civil disobedience. \$\endgroup\$ – vnp Dec 23 '17 at 2:32
  • \$\begingroup\$ I was thinking of C11 - 7.31.2. But I think you're safe here even in C, because that refers to is followed by a lowercase letter, and underscore is not a letter. And in C++, we use <cctype> rather than <ctype.h>... :-) \$\endgroup\$ – Toby Speight Jan 8 '18 at 14:07
5
\$\begingroup\$

Prefer Measurement to Guessing

Since there's some disagreement over whether it's better to sort the strings and compare, or count in something like a map and compare them, let's start by measuring the actual performance of the two:

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <cctype>
#include <cassert>
#include "timer.h"

std::string clean(std::string const &in) {
    std::string ret;
    std::remove_copy_if(in.begin(), in.end(),
        std::back_inserter(ret),
        [](unsigned char ch) { return ::isspace(ch); });
    return ret;
}

bool is_anagram1(std::string const &in1, std::string const &in2) {
    auto a1 = clean(in1);
    auto a2 = clean(in2);
    std::sort(a1.begin(), a1.end());
    std::sort(a2.begin(), a2.end());

    return a1 == a2;
}

bool is_anagram2(std::string const &in1, std::string const &in2) {
    std::unordered_map<char, size_t> counts1;
    std::unordered_map<char, size_t> counts2;

    auto a1 = clean(in1);
    auto a2 = clean(in2);

    for (auto const &a : a1)
        ++counts1[a];

    for (auto const &a : a2)
        ++counts2[a];

    return counts1 == counts2;
}

struct test_case {
    std::string a;
    std::string b;
    bool expected;
};

int main() {
    std::vector<test_case> tests{
        { "off", "off", true },
        { "off", "of f", true},
        { "off", "oof", false},
        { "this is a longer string than the others", "this is a longer string than the others", true },
        { "this is a longre string thna the ohters", "this is a longer string than the others", true },
    };

    for (auto const &test : tests) {
        assert(timer(is_anagram1, "using sort", test.a, test.b) == test.expected);
        assert(timer(is_anagram2, "using map", test.a, test.b) == test.expected);
        std::cout << "\n";
    }
}

Compiled with VC++ 2017, I get results like this:

using sort time: 1 uS
using map time: 4 uS

using sort time: 2 uS
using map time: 5 uS

using sort time: 1 uS
using map time: 9 uS

using sort time: 4 uS
using map time: 26 uS

using sort time: 3 uS
using map time: 10 uS

Testing with g++ and CLang++ yields similar results--at least for these inputs, sorting in place beats a map with a fairly high degree of dependability.

Style

A few other style points I don't see mentioned elsethread:

  1. Names: I'm not particularly fond of usr1 and usr2 as names. It's been quite a while since mass storage was expensive enough to prefer these over (for example) input_1 and input_2.
  2. It's probably worth having the anagram checker remove the spaces from the input strings, since (at least as most people use the word) part of the definition of an anagram is that white space should be ignored.
  3. In messages to the user, grammar counts. String is anagrams should be more like Strings are anagrams.
\$\endgroup\$
  • \$\begingroup\$ A std::map is quite a heavyweight object for counting (compared to, e.g. std::array<size_t, UCHAR_MAX>). It would be great if you extended the performance measurements to more implementations (I should do that myself, but I'm heading AFK for a couple of weeks). Regardless, this is excellent advice: measure, don't guess. \$\endgroup\$ – Toby Speight Dec 22 '17 at 12:47
  • \$\begingroup\$ @TobySpeight: Good point, but unfortunately I'm leaving to visit relatives as well, so it'll probably be a while before it gets extended... \$\endgroup\$ – Jerry Coffin Dec 22 '17 at 14:14
  • \$\begingroup\$ Where does the timer function come from? \$\endgroup\$ – mkrieger1 Dec 23 '17 at 21:33
3
\$\begingroup\$

Check the length before sorting

It takes constant time to determine the length of a string but std::sort is \$O(N\log(N))\$. If the lengths don't match then you don't have to sort.


Pass strings to anagrams() by const reference

You are passing the arguments to anagrams() by value, which means you have to copy the strings. That function doesn't need a copy of the strings nor does it need to modify them, so you can pass them as const references to avoid the copy:

bool anagrams(const std::string& usr1, const std::string& usr2)

End the for loop with pos < usr1.length()

Instead of ending the for loop with pos<= usr1.length()-1, it's more idiomatic to use pos < usr1.length(). It requires less typing and avoids an unnecessary subtraction.


Alternative solution

I would map each character in the two strings to the number of times it occurs. If all the characters in one string are present in the other (the two maps have the same character keys) and all the characters occur the same number of times, then the strings are anagrams. Once you've built the strings' maps you can use std::map::operator== to check that the two maps are equal.

Here's a demo:

#include <iostream> 
#include <string>
#include <cctype>
#include <map>

void build_char_map(const std::string& s, std::map<char, int>& char_map) {
    for (std::string::size_type pos = 0; pos < s.size(); pos++) {
        char c = s[pos];

        if (!std::isspace(static_cast<int>(c))) {
            char_map[c]++;
        }
    }
}

bool is_anagram(const std::string& s1, const std::string& s2) {
    std::map<char, int> characters1, characters2;

    build_char_map(s1, characters1);
    build_char_map(s2, characters2);

    return characters1 == characters2;
}

void print(const std::string& s1, const std::string& s2) {
    std::cout << "\"" << s1 << "\"" << " and " << "\"" << s2 << "\"" << " are ";

    if (!is_anagram(s1, s2)) {
        std::cout << "not ";
    }

    std::cout << "anagrams\n";
}

int main() {
    std::string s1("foo");
    std::string s2("oof");

    print(s1, s2);

    s2 = "off";

    print(s1, s2);

    return 0;
}

Output:

"foo" and "oof" are anagrams
"foo" and "off" are not anagrams
\$\endgroup\$
  • \$\begingroup\$ Actually libc++ had a bug for some time where particular input would cause std::sort to degrade very quickly. I believe it is fixed now, as it is switched to introsort. \$\endgroup\$ – Incomputable Dec 9 '17 at 9:15
  • 1
    \$\begingroup\$ "pos < usr1.length()" not only is it faster to type, coders who use this style make fewer errors \$\endgroup\$ – Snowbody Dec 9 '17 at 23:02
2
\$\begingroup\$

Algorithm

I think you can do better on the algorithm.

  • Remove all the space from both input strings.
  • Sort both of the strings.
  • Return false if the lengths differ.
  • Return true if all char matches.

Complexity of those steps are:

  • O(n)
  • O(n.log(n))
  • O(1)
  • O(1)

I think an easier way is to count the number of each letter.

  • Count
  • Compare

Complexity

  • O(n)
  • O(m) => m small or fixed size => O(1)

Code Review

You do steps (1) and (2) outside the anagram() function.

You pass the strings by value thus causing a copy of each string.

In main you use standard algorithms to loop over the strings but in anagram() you use a manual loop. You could simply have done a string comparison at that point.

// this does the same.
bool anagrams(std::string usr1,std::string usr2) {
    return usr1 == usr2;
}
\$\endgroup\$
  • \$\begingroup\$ Shouldn't Return true if all char matches be of O(n), too? \$\endgroup\$ – Raimund Krämer Dec 22 '17 at 10:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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