C++ 使用C++检查两个字符串是否是字谜

Check whether two strings are anagrams using C++

提问by user2688416

The program below I came up with for checking whether two strings are anagrams. Its working fine for small string but for larger strings ( i tried : listened , enlisted ) Its giving me a 'no !'

下面是我想出的用于检查两个字符串是否为字谜的程序。它适用于小字符串但适用于较大的字符串（我试过：听过，入伍）它给了我一个“不！”

Help !

帮助 ！

#include<iostream.h> 
#include<string.h>
#include<stdio.h>

int main()
{
    char str1[100], str2[100];
    gets(str1);
    gets(str2);
    int i,j;
    int n1=strlen(str1);
    int n2=strlen(str2);
    int c=0;
    if(n1!=n2)
    {
          cout<<"\nThey are not anagrams ! ";
          return 0;
    }
    else 
    {
         for(i=0;i<n1;i++)
             for(j=0;j<n2;j++)
                 if(str1[i]==str2[j])
                     ++c;
    }
    if(c==n1)
        cout<<"yes ! anagram !! ";
    else 
        cout<<"no ! ";

    system("pause");
    return 0;
}

回答by juanchopanza

I am lazy, so I would use standard library functionality to sort both strings and then compare them:

我很懒，所以我会使用标准库功能对两个字符串进行排序，然后比较它们：

#include <string>
#include <algorithm>

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

A small optimization could be to check that the sizes of the strings are the same before sorting.

一个小的优化可能是在排序之前检查字符串的大小是否相同。

But if this algorithm proved to be a bottle-neck, I would temporarily shed some of my laziness and compare it against a simple counting solution:

但是如果这个算法被证明是一个瓶颈，我会暂时摆脱一些我的懒惰，并将其与一个简单的计数解决方案进行比较：

1. Compare string lengths
2. Instantiate a count map, std::unordered_map<char, unsigned int> m
3. Loop over s1, incrementing the count for each char.
4. Loop over s2, decrementing the count for each char, then check that the count is 0

1. 比较字符串长度
2. 实例化一个计数图， std::unordered_map<char, unsigned int> m
3. 循环s1，增加每个的计数char。
4. 循环s2，递减每个的计数char，然后检查计数是否为0

回答by Joni

The algorithm also fails when asked to find if aaand aaare anagrams. Try tracing the steps of the algorithm mentally or in a debugger to find why; you'll learn more that way.

当被要求查找是否aa和aa是字谜时，该算法也会失败。尝试在心里或在调试器中跟踪算法的步骤以找出原因；这样你会学到更多。

By the way.. The usual method for finding anagrams is counting how many times each letter appears in the strings. The counts should be equal for each letter. This approach has O(n) time complexity as opposed to O(n2).

顺便说一句.. 寻找字谜的常用方法是计算每个字母在字符串中出现的次数。每个字母的计数应该相等。这种方法的时间复杂度为 O(n)，而不是 O(n2)。

回答by Suraj

bool areAnagram(char *str1, char *str2)
{
    // Create two count arrays and initialize all values as 0
    int count1[NO_OF_CHARS] = {0};
    int count2[NO_OF_CHARS] = {0};
    int i;

    // For each character in input strings, increment count in
    // the corresponding count array
    for (i = 0; str1[i] && str2[i];  i++)
    {
        count1[str1[i]]++;
        count2[str2[i]]++;
    }

    // If both strings are of different length. Removing this condition
    // will make the program fail for strings like "aaca" and "aca"
    if (str1[i] || str2[i])
      return false;

    // Compare count arrays
    for (i = 0; i < NO_OF_CHARS; i++)
        if (count1[i] != count2[i])
            return false;

    return true;
}

回答by Adrian Rosoga

I see 2 main approaches below:

我看到以下两种主要方法：

1. Sort then compare
2. Count the occurrences of each letter

1. 排序然后比较
2. 计算每个字母出现的次数

It's interesting to see that Suraj's nice solution got one point (by me, at the time of writing) but a sort one got 22. The explanation is that performance wasn't in people's mind - and that's fine for short strings.

有趣的是，看到 Suraj 的好解决方案得到了 1 分（在我写这篇文章的时候），但有一个得到了 22 分。解释是性能不在人们的脑海中 - 这对于短字符串来说很好。

The sort implementation is only 3 lines long, but the counting one beats it square for long strings. It is much faster (O(N) versus O(NlogN)). Got the following results with 500 MBytes long strings.

排序实现只有 3 行长，但对于长字符串而言，计数一比它方。它要快得多（O(N) 与 O(NlogN)）。使用 500 MBytes 长字符串得到以下结果。

1. Sort- 162.8 secs
2. Count- 2.864 secs
3. Multi threaded Count- 3.321 secs

1. 排序- 162.8 秒
2. 计数- 2.864 秒
3. 多线程计数- 3.321 秒

The multi threaded attempt was a naive one that tried to double the speed by counting in separate threads, one for each string. Memory access is the bottleneck and this is an example where multi threading makes things a bit worse.

多线程尝试是一种天真的尝试，它试图通过在单独的线程中计数来使速度加倍，每个线程一个。内存访问是瓶颈，这是一个多线程使事情变得更糟的例子。

I would be happy to see some idea that would speed up the count solution (think by someone good with memory latency issues, caches).

我很高兴看到一些可以加速计数解决方案的想法（想想那些擅长内存延迟问题、缓存的人）。

回答by NikaTsanka

Here is the simplest and fastest way to check for anagrams

这是检查字谜的最简单和最快的方法

bool anagram(string a, string b) {
    int a_sum = 0, b_sum = 0, i = 0;
    while (a[i] != '
#include<stdio.h>
#include<string.h>
int is_anagram(char* str1, char* str2){
    if(strlen(str1)==strspn(str1,str2) && strlen(str1)==strspn(str2,str1) &&
    strlen(str1)==strlen(str2))
    return 1;
    return 0;
}
int main(){
    char* str1 = "stream";
    char* str2 = "master";
    if(is_anagram(str1,str2))
    printf("%s and %s  are anagram to each other",str1,str2);
    else
    printf("%s and %s  are not anagram to each other",str1,str2);
    return 0;
}
') {
        a_sum += (int)a[i]; // (int) cast not necessary
        b_sum += (int)b[i];
        i++;
    }
    return a_sum == b_sum;
}

Simply adds the ASCII values and checks if the sums are equal.

只需添加 ASCII 值并检查总和是否相等。

For example: string a = "nap" and string b = "pan"
a_sum = 110 + 97 + 112 = 319
b_sum = 112 + 97 + 110 = 319

例如：string a = "nap" and string b = "pan"
a_sum = 110 + 97 + 112 = 319
b_sum = 112 + 97 + 110 = 319

回答by Kumar

#include<iostream>
#include<unordered_map>
using namespace std;

int checkAnagram (string &str1, string &str2)
{
    unordered_map<char,int> count1, count2;
    unordered_map<char,int>::iterator it1, it2;
    int isAnagram = 0;

    if (str1.size() != str2.size()) {
        return -1;
    }

    for (unsigned int i = 0; i < str1.size(); i++) {
        if (count1.find(str1[i]) != count1.end()){
            count1[str1[i]]++;
        } else {
            count1.insert(pair<char,int>(str1[i], 1));
        }
    }

    for (unsigned int i = 0; i < str2.size(); i++) {
        if (count2.find(str2[i]) != count2.end()) {
            count2[str2[i]]++;
        } else {
            count2.insert(pair<char,int>(str2[i], 1));
        }
    }

    for (unordered_map<char, int>::iterator itUm1 = count1.begin(); itUm1 != count1.end(); itUm1++) {
        unordered_map<char, int>::iterator itUm2 = count2.find(itUm1->first);
        if (itUm2 != count2.end()) {
            if (itUm1->second != itUm2->second){
                isAnagram = -1;
                break;
            }
        }
    }

    return isAnagram;
}

int main(void)
{
    string str1("WillIamShakespeare");
    string str2("IamaWeakishSpeller");

    cout << "checkAnagram() for " << str1 << "," << str2 << " : " << checkAnagram(str1, str2) << endl;

    return 0;
}

回答by SuperEye

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

//
// return a sorted copy of a string
//
std::string sorted(std::string in)
{
    std::sort(in.begin(), in.end());
    return in;
}

//
// check whether xor-ing the values in two ranges results in zero.
// @pre first2 addresses a range that is at least as big as (last1-first1)
//
bool xor_is_zero(std::string::const_iterator first1,
                 std::string::const_iterator last1,
                 std::string::const_iterator first2)
{
    char x = 0;
    while (first1 != last1) {
        x ^= *first1++;
        x ^= *first2++;
    }
    return x == 0;
}

//
// deduce whether two strings are the same length
//
bool same_size(const std::string& l, const std::string& r)
{
    return l.size() == r.size();
}

//
// deduce whether two words are anagrams of each other
// I have passed by const ref because we may not need a copy
//
bool is_anagram(const std::string& l, const std::string& r)
{
    return same_size(l, r)
    && xor_is_zero(l.begin(), l.end(), r.begin())
    && sorted(l) == sorted(r);
}

// test

int main()  {

    using namespace std;

    auto s1 = "apple"s;
    auto s2 = "eppla"s;

    cout << is_anagram(s1, s2) << '\n';

    s2 = "pppla"s;

    cout << is_anagram(s1, s2) << '\n';

    return 0;
}

回答by Richard Hodges

It's funny how sometimes the best questions are the simplest.

有趣的是，有时最好的问题却是最简单的。

The problem here is how to deduce whether two words are anagrams - a word being essentially an unsorted multiset of chars.

这里的问题是如何推断两个词是否是字谜——一个词本质上是一个未排序的多组字符。

We know we have to sort, but ideally we'd want to avoid the time-complexity of sort.

我们知道我们必须排序，但理想情况下我们希望避免 sort 的时间复杂性。

It turns out that in many cases we can eliminate many words that are dissimilar in linear timeby running through them both and XOR-ing the character values into an accumulator. The total XOR of all characters in both strings must be zero if both strings are anagrams, regardless of ordering. This is because anything xored with itself becomes zero.

事实证明，在许多情况下，我们可以通过遍历它们并将字符值异或到累加器中来消除许多线性时间不同的单词。如果两个字符串都是字谜，则无论排序如何，两个字符串中所有字符的总异或必须为零。这是因为任何与自身异或的东西都会变为零。

Of course the inverse is not true. Just because the accumulator is zero does not mean we have an anagram match.

当然，反过来是不正确的。仅仅因为累加器为零并不意味着我们有一个字谜匹配。

Using this information, we can eliminate many non-anagrams without a sort, short-circuiting at least the non-anagram case.

使用这些信息，我们可以在没有排序的情况下消除许多非字谜，至少使非字谜情况短路。

1
0

expected:

预期的：

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

using namespace std;

bool is_anagram( const string a, const string b ){
    std::map<char, int> m;
    int count = 0;

    for (int i = 0; i < a.length(); i++) {
        map<char, int>::iterator it = m.find(a[i]);
        if (it == m.end()) {
            m.insert(m.begin(), pair<char, int>(a[i], 1));
        } else {
            m[a[i]]++;
        }
    }

    for (int i = 0; i < b.length(); i++) {
        map<char, int>::iterator it = m.find(b[i]);
        if (it == m.end()) {
            m.insert(m.begin(), pair<char, int>(b[i], 1));
        } else {
            m[b[i]]--;
        }
    }

    if (a.length() <= b.length()) {
        for (int i = 0; i < a.length(); i++) {
            if (m[a[i]] >= 0) {
                count++;
            } else
                return false;
        }
        if (count == a.length() && a.length() > 0)
            return true;
        else
            return false;
    } else {
        for (int i = 0; i < b.length(); i++) {
            if (m[b[i]] >= 0) {
                count++;
            } else {
                return false;
            }
        }
        if (count == b.length() && b.length() > 0)
            return true;
        else
            return false;
    }
    return true;
}

回答by Abdel Hechavarria Diaz

In this approach I took care of empty strings and repeated characters as well. Enjoy it and comment any limitation.

在这种方法中，我还处理了空字符串和重复字符。享受它并评论任何限制。

// Anagram. Two words are said to be anagrams of each other if the letters from one word can be rearranged to form the other word. 
// From the above definition it is clear that two strings are anagrams if all characters in both strings occur same number of times. 
// For example "xyz" and "zxy" are anagram strings, here every character 'x', 'y' and 'z' occur only one time in both strings. 

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

using namespace std;

bool IsAnagram_1( string w1, string w2 )
{
    // Compare string lengths
    if ( w1.length() != w2.length() )
        return false;

    sort( w1.begin(), w1.end() );
    sort( w2.begin(), w2.end() );

    return w1 == w2;
}

map<char, size_t> key_word( const string & w )
{
    // Declare a map which is an associative container that will store a key value and a mapped value pairs
    // The key value is a letter in a word and the maped value is the number of times this letter appears in the word
   map<char, size_t> m;

   // Step over the characters of string w and use each character as a key value in the map
   for ( auto & c : w )
   {
        // Access the mapped value directly by its corresponding key using the bracket operator
        ++m[toupper( c )];  
   }

   return ( m );
}


bool IsAnagram_2( const string & w1, const string & w2 )  
{
    // Compare string lengths
    if ( w1.length() != w2.length() )
        return false;

    return ( key_word( w1 ) == key_word( w2 ) );
}


bool IsAnagram_3( const string & w1, const string & w2 )  
{
    // Compare string lengths
    if ( w1.length() != w2.length() )
        return false;

    // Instantiate a count map, std::unordered_map<char, unsigned int> m
    unordered_map<char, size_t> m;

    // Loop over the characters of string w1 incrementing the count for each character
   for ( auto & c : w1 )
   {
        // Access the mapped value directly by its corresponding key using the bracket operator
        ++m[toupper(c)];    
   }

    // Loop over the characters of string w2 decrementing the count for each character
   for ( auto & c : w2 )
   {
        // Access the mapped value directly by its corresponding key using the bracket operator
        --m[toupper(c)];    
   }

   // Check to see if the mapped values are all zeros
   for ( auto & c : w2 )
   {
        if ( m[toupper(c)] != 0 )
            return false;
   }

   return true;
}


int main( )
{
    string word1, word2;

    cout << "Enter first word: ";
    cin >> word1;

    cout << "Enter second word: ";
    cin >> word2;

    if ( IsAnagram_1( word1, word2 ) )
        cout << "\nAnagram" << endl;
    else 
        cout << "\nNot Anagram" << endl;


    if ( IsAnagram_2( word1, word2 ) )
        cout << "\nAnagram" << endl;
    else 
        cout << "\nNot Anagram" << endl;


    if ( IsAnagram_3( word1, word2 ) )
        cout << "\nAnagram" << endl;
    else 
        cout << "\nNot Anagram" << endl;

    system("pause");

    return 0;
}

回答by MikhailJacques

Try this:

尝试这个：

##代码##