c++ - 使用 C++ 检查两个字符串是否是变位词

Question

我想出下面的程序来检查两个字符串是否是变位词。它适用于小字符串但适用于较大的字符串(我试过:听过，入伍)它给了我一个“不!”

帮助!

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

Answer 1

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

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

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

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

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