c++ - 如何优化此 Codewars c++ 代码？

Question

我正在用 C++ 进行 Codewars 培训，我的代码运行良好，但它说它不够快，无法通过所有测试。在本次培训中，我需要检查 str1 字符的一部分是否可以重新排列以匹配 str2(全部作为参数传递并且是 const)。非常简单的主题，但我该如何优化它？这是我的代码:

bool scramble(const std::string& s1, const std::string& s2){
   int j = 0;
   int i = 0;
   size_t good_count = 0;
   char tmp[s1.size()];

   std::strcpy(tmp, s1.c_str());
   while (tmp[i]) {
        if (tmp[i] == s2[j]) {
            std::memmove(&tmp[i], &tmp[i + 1], strlen(tmp) - i);
            j++;
            good_count++;
            i = 0;
        } else
            i++;
      }
     return good_count == s2.size() ? true : false;
}

我想到了memmove功能，是不是太慢了？我尝试使用 std::remove 和 str.erase 但我得到了相同的结果。
感谢您的帮助 !

Answer 1

您当前的方法是实际进行重新排列，并进行大量内存移动。但实际上你可以只计算 S2 中每个字母的数量，然后遍历 S1，直到你积累了相同数量的字母。

Achtung 完全未经测试的代码。

// assuming all is lowercase
int matches = S2.length();
std::array<int, 256> chars { 0 };
for (char alfa : S2) {
  chars[alfa]++;
}
for (char alfa : S1) {
  if (chars[alfa]-->0) {
    if (!--matches)
      return true;
  }
}