我如何优化这个 Codewars c++ 代码？

Question

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

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

我如何优化这个 Codewars c++ 代码？

How can i optimize this Codewars c++ code?

c++

string

optimization

scramble