Оптимизация кода на время

Question

Помогите с оптимизацией кода, я в этом не силён. На сайте codewars проходил задание и мой код работает со всеми тестами кроме Производительности, пишет Execution Timed Out (12000 ms). Как его можно оптимизировать?

bool scramble(const std::string& s1, const std::string& s2) {
    std::string temp1{};
    std::string temp2{s1};
    for (unsigned long i = 0; i < s2.size(); ++i) {
        for (unsigned long j = 0; j < temp2.size(); ++j) {
            if (s2[i] == temp2[j]) {
                temp1.push_back(s2[i]);
                temp2.erase(std::find(temp2.begin(), temp2.end(), temp2[j]));
              break;
            }
        }
    }
    return (s2 == temp1)? true : false;
}

Входные данные:

scramble("rkqodlw", "world"), Equals(true);
scramble("cedewaraaossoqqyt", "codewars"), Equals(true);
scramble("katas", "steak"), Equals(false);
scramble("scriptjavx", "javascript"), Equals(false);
scramble("scriptingjava", "javascript"), Equals(true);
scramble("scriptsjava", "javascript"), Equals(true);
scramble("javscripts", "javascript"), Equals(false);
scramble("aabbcamaomsccdd", "commas"), Equals(true);
scramble("commas", "commas"), Equals(true);
scramble("sammoc", "commas"), Equals(true);

Само задание тыц

Answer 1

Как я и думал, простого решения вполне достаточно:

bool scramble(const std::string& s1, const std::string& s2)
{
    std::string ss1 = s1, ss2 = s2;
    std::sort(ss1.begin(),ss1.end());
    std::sort(ss2.begin(),ss2.end());
    return std::includes(ss1.begin(),ss1.end(),ss2.begin(),ss2.end());
}

Главное правило — оптимизация должна начинаться с алгоритма, а не с кода...

Answer 2

Codewars разрешает поменять сигнатуру, лишь бы работало, так что код Harry можно упростить до

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

БЛОГ НА HUSL

Оптимизация кода на время

Ответы (2 шт):