Liens utiles

How to find time complexity of an algorithm?

TEST#1

Créer une boucle for et dès qu’il trouve la bonne lettre dans str1, il va la transformer en char “&” pour éviter de rematch la même lettre. Ca évite les faux positifs.

function scramble(str1, str2) {
  const length = str2.length;
  const index = [];
  
  for(let i = 0; i < length; i++) {
    let indicator = str1.search(str2[i]);
    if(indicator === -1) {
      return false;
    };
    str1 = str1.substring(0, indicator) + "&" + str1.substring(indicator + 1);
    index.push(indicator);
  }
  return true;
}

TEST#2

Tentative sur un tableau et enlever le char dans le tableau str2 si il le trouve. On itère sur str1 pour éviter de recheck la même lettre.

function scramble(str1, str2) {
  if(str1.length < str2.length) return false;
  
  let _str2 = str2.split("");
  
  
  str1.split("").forEach((element) => {
    if(_str2.includes(element)) _str2.splice(_str2.indexOf(element), 1)
  })
  
  return _str2.length == 0;
}

TEST#3 [WINNER]

C’est la meilleure complexité que j’ai pu trouver. O(n), il va compter le nombre de lettre qu’il y a dans chaque string et si le nombre de char de la str1 est supérieur au nombre de char de la str2, il y a forcément match. On check ca sur l’objet obj 2 car c’est le comparant.

const countStr = (str) => {
    const obj = {};
    for (const char of str) {
        obj[char] = (obj[char] || 0) + 1;
    }
    return obj;
}
const scramble = (str1, str2) => {
    const [obj1, obj2] = [str1, str2].map(countStr);
    return (  
        Object.entries(obj2).every(([key, val]) => obj1[key] >= val)
    );
};