代码审查,C++,Anagram方法

Question

我正在从"破解编码面试"一书中做一些练习题,并希望让一些人查看我的代码以查找错误和优化.任何反馈将不胜感激.

问题:编写一个方法来判断两个字符串是否是字谜.

/*
Time complexity: O(n^2)
Space complexity: O(n)
*/
bool IsAnagram(std::string str1, std::string str2)
{
    if(str1.length() != str2.length())
        return false;
    for(int i = 0; i < str1.length();i++)
    {
        bool found = false;
        int j = 0;
        while(!found && j < str2.length())
        {
            if(str1[i] == str2[j])
            {
                found = true;
                str2[j] = NULL;
            }
            j++;
        }
        if(!found)
            return false;
    }
    return true;
}

Answer 1

这通常更有效

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

bool IsAnagram(std::string& str1, std::string& str2)
{
  if(str1.length() != str2.length())
    return false;

  std::sort(str1.begin(), str1.end());
  std::sort(str2.begin(), str2.end());

  return str1.compare(str2) == 0;
}

int main(int argc, char* argv[])
{
  std::string an1("army");
  std::string an2("mary");
  if(IsAnagram(an1, an2)) 
    std::cout << "Hooray!\n";

    return 0;
}

对于那些不喜欢变异字符串的人来说,这可能是一个更好的选择.可以删除对参数1和2的引用,也可以在此处复制函数内部.这样,参数可以是常量.

bool IsAnagram2(const std::string& str1, const std::string& str2)
{
   if(str1.length() != str2.length())
      return false;

   std::string cpy1(str1), cpy2(str2);

   std::sort(cpy1.begin(), cpy1.end());
   std::sort(cpy2.begin(), cpy2.end());

   return cpy1.compare(cpy2) == 0;
}