Как ускорить while loop?

Question

[Quintis]

Написал функцию для прохождения задания - https://www.codewars.com/kata/55c04b4cc56a697bb000...
но не могу пройти так как выбивает ошибка Execution Timed Out (12000 ms)
Как ускорить while loop ?

function scramble(str1, str2) {
  let finishSTR = str2.split("").filter(el=>{return el.match(/[a-z]/)});
  let startSTR = str1.split("").filter(el=>{return el.match(/[a-z]/)});
  let result = true;
  let len = finishSTR.length;
  while (len--) {
    console.log(len);
    let el = finishSTR[len]
    if (startSTR.includes(el)){
      startSTR[startSTR.indexOf(el)] = null
    } else {
      result= false
      return false
    }
  }

  console.log(result);
  return result;
  //code me
}
scramble("rkqodlw", "world");

Comments

[Lynn «Кофеман»]

Для начала убрать console.log(len)

[Ярослав Иванов]

Два ретурна?

[Quintis]

Ярослав Иванов,

result= false
      return false

[Ярослав Иванов]

Quintis, теперь один. Что за магия.

[RAX7]

Делаешь словарик из str2 типа:

{
  a: 2,
  b: 7,
  z: 4
}

проходишь циклом по str1 и из словаря вычитаешь единицу для текущей буквы, как только счетчик станет меньше нуля или такой буквы нет в словаре return false иначе true

[Mazino]

У вас в коде был не безопасный while(len--), если len == 0, то while((-1)--) {}
в итоге бесконечный цикл.

Answer 1

[Сергей Соколов]

includes() и indexOf() каждый раз, считайте, пробегают, в среднем, по полстроки.
Представьте, что там дико длинные строки, гигабайтные.
Поэтому алгоритм желательно построить так, чтобы по каждой Войне и Миру пройтись 1 раз или меньше.

Условие хорошо сужает возможные символы до всего 26 букв латинского алфавита a..z

Рабочее решение под

спойлером

Например, можно создать массив из 26 счётчиков и заполнять их из первой строки и опустошать из второй.
Вот такое моё решение прошло тест:

function scramble(str1, str2) {
  if (str1.length < str2.length) return false;
  const a = Array(26).fill(0);
  for (let c of str1) a[c.charCodeAt(0) - 97]++;
  for (let c of str2) a[c.charCodeAt(0) - 97]--;
  for (let n of a) if (n < 0) return false;
  return true;
}

* 97 это ASCII-код маленькой латинской "a"

Answer 2

[galaxy]

sort -> join и потом тупо сравнить две строки, безо всяких циклов

Comments

[Lynn «Кофеман»]

Тупо сравнить нельзя, там могут быть лишние буквы. Но да, будет один линейный цикл.

[Quintis]

сравнить через .localeCompare() ?

[galaxy]

Я условие не дочитал, сравнить не получится.

[galaxy]

Вот так (но на тонкого - 9сек :))

function scramble(str1, str2) {
  var s1 = {}, s2 = {};
  str1.split("").forEach((e) => {
    s1[e] = e in s1 ? s1[e]+1 : 1;
  });
  str2.split("").forEach((e) => {
    s2[e] = e in s2 ? s2[e]+1 : 1;
  });
 
  for(key in s2) {
    if (!(key in s1) || s1[key] < s2[key])
      return false
  }
  return true;
}

[Quintis]

galaxy, Спасибо , прошло !

[Quintis]

galaxy, я так понял что вы строку кодируете в обьект , в котором ключ это буква а значение это сколько екземпляров букв есть ?

[galaxy]

Конечно