Finding if two strings are anagrams or not in C++

Question

I am trying to write a code that checks if a string is an anagram or not. However I keep getting error's That "you cannot assign to a variable that is constant". I understand what it means, but what is the walkaround/solution for this?

    #include <iostream>
    #include <algorithm>
    #include <string>
    using namespace std;

    bool check_str(const string& a, const string& b)
    {

    // cant be the same if the lenghts are not the same 
    if (a.length() != b.length())
        return false;
    //both the strings are sorted and then char by char compared
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] != b[i]) //char by char comparison
            return false;
    }

    return true;
}

int main()
{
    string a = "apple";
    string b = "ppple";

    if (check_str(a, b))
    {
        cout << "Yes same stuff" << endl;
    }
    else
    {
        cout << "Not the same stuff" << endl;
    }
    system("pause");
 }

Along with the answers you've already gotten, note that you don't need to explicitly compare char by char. Just `return a == b;` will compare the characters individually. — Jerry Coffin, Dec 15 '15 at 17:51
What is the point of that edit? Also, as already mentioned, this `if ... else...` you just added at the end of your function can be reduced to `return a == b;`. — Baum mit Augen, Dec 15 '15 at 18:07

Baum mit Augen · Answer 1 · 2015-12-15T17:59:36.100

You try to std::sort your input strings which would modify them, but you also declared them const (by passing them as const std::string&) which prohibits modifying them.

Pass by value, i.e.

bool check_str(string a, string b)

or non-const reference, i.e.

bool check_str(string& a, string& b)

instead. The latter will modify your original strings, the former won't. Also, the first variant will accept temporaries and the second one will not.

In my opinion, passing by value would be the way to go here as some function called check_str modifying its inputs seems counter intuitive.

Last remark: As already mentioned in the comments, you do not need to use a loop to compare the strings, you can simply compare them with a == b.

score 0 · Answer 2 · answered Dec 15 '15 at 17:43

0

Both strings are constant references, but you try to sort them. That obviously changes the strings, therefore is not valid. You could make copies of your string, or pass by value instead of reference.

answered Dec 15 '15 at 17:43

cehnehdeh

527
3
13

xhg · Answer 3 · 2015-12-15T18:27:59.317

0

Since the string are const, you can not sort them. Make a copy of them may be a workaround, but I think when the string are large, it make the space complexity O(n), and if you want to sort, make the time complexity O(nlgn). I prefer this approach, time O(n), space O(1):

#define SIZE CHAR_MAX + 1
bool check(const char a[], const char b[]) {
    if (strlen(a) != strlen(b)) return false;
    int length = strlen(a);
    int char_count_a[SIZE] = {0};
    int char_count_b[SIZE] = {0};
    for (int i = 0; i < length; ++i) char_count_a[a[i]]++;
    for (int i = 0; i < length; ++i) char_count_b[b[i]]++;
    for (int i = 0; i < SIZE; ++i) 
        if (char_count_a[i] != char_count_b[i]) return false;
    return true;
}

edited Dec 15 '15 at 18:27

answered Dec 15 '15 at 17:54

xhg

1,850
2
21
35

1

Are you sure `sizeof(char)` is what you want there, and not something like `CHAR_MAX + 1`? – Benjamin Lindley Dec 15 '15 at 18:21
@BenjaminLindley yep... Mistake – xhg Dec 15 '15 at 18:27

score 0 · Answer 4 · answered Dec 15 '15 at 18:01

0

Just for fun:

#include <algorithm>
#include <string>

bool check_str(const std::string& a, const std::string& b) {
    if (a == b)
        return true;
    std::string temp(a);
    std::sort(temp.begin(), temp.end());
    while (std::next_permutation(temp.begin(), temp.end())
        if (temp == b)
            return true;
    return false;
}

answered Dec 15 '15 at 18:01

Pete Becker

74,985
8
76
165

Ye olde `O(n!)` algorithme. – Barry Dec 15 '15 at 18:04
It will take days to check strings with hundreds chars, oops – xhg Dec 15 '15 at 18:04
awesome solution - now write it in ook! :-)) – Richard Hodges Dec 15 '15 at 18:15
@Barry - yes, but it only copies one string instead of two. – Pete Becker Dec 15 '15 at 18:44

score 0 · Answer 5 · answered Dec 15 '15 at 18:14

Simplest working code, with const reference argument

bool check_str(std::string const &a, std::string const &b) {
    if (a == b)     return true;
    std::string t1(a);
    std::string t2(b);
    std::sort(t1.begin(), t1.end());
    std::sort(t2.begin(), t2.end());
    if(t1 == t2)    return true;
    return false;
}

or with pass-by-value

bool check_str(std::string a,std::string b) {
    if (a == b)     return true;
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    if(a == b)    return true;
    return false;
}

Finding if two strings are anagrams or not in C++

5 Answers5