Effective way to find two string are anagrams

Question

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;
}

Answer 1

• 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.

Answer 2

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.

Answer 3

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

Answer 4

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;
}