编写置乱函数的简单方法

Question

对于函数scramble(str1,str2)，我想要一种更简单的方法，以便如果str1的一部分可以被安排成匹配str2。请注意，所有要使用的字母都是小写的。我使用了下面的代码，它成功了，但是任何人都能给我一个更简单的方法吗？

function scramble(str1,str2){
     str2 = str2.split('');
     str1 = str1.split('');
     let arr = [] , condition ;
     arr.length = str2.length;

     for(let i =0;i<str2.length;i++){
      for(let a= 0 ;a<str1.length;a++){
       if(str2[i] == str1[a]){
        str1[a] = '';
        arr[i] = 'true'
         break;
       }
      }
     }
      for(let i = 0;i<arr.length;i++){
       if(arr[i] == undefined){
        return false
       }
      }
      return true
    }
  console.log(scramble('rkqodlw','world')) //true;
  console.log(scramble('cedewaraaossoqqyt','codewars'))//true
  console.log(scramble('katas','steak')) //false
  console.log(scramble('scriptjava','javascript'))//true
  console.log(scramble('scriptingjava','javascript'))//true
  console.log(scramble('scriptsjava','javascripts')//true
  console.log(scramble('jscripts','javascript')) //false
  console.log(scramble('aabbcamaomsccdd','commas')) //true

Answer 1

您可以对str1中的所有字符进行计数，然后遍历str2，减少计数，如果达到0，则返回false：

 const count = {};

 for(const char of str1)
   count[char] = (count[char] || 0) + 1;

for(const char of str2)
  if(!count[char]--) return false;

return true;

Answer 2

这个问题是检查一个元素集是否是另一个元素子集的泛型问题的一个版本。

解决此任务的基本步骤是获取set1的第一个元素，并检查它是否存在于set2中。如果不是，我们返回false。如果是，我们用set2检查下一个元素，减去匹配的元素；基本情况是当我们有一个空集时(因为空集是任何集合的子集)。

function check(str1, str2) {
  if (str2.length === 0) {
     return true;
  }
  const [first, ...rest] = str1;
  const idx = str2.indexOf(first);
  if (idx !== -1) {
    const str2Rest = [...str2.slice(0, idx), ...str2.slice(idx+1)];
    return check(rest, str2Rest);
  }
  return true;
}

您还可以先对字符串进行排序，然后两者都知道匹配的字符可能仅位于当前位置或较高的索引处。

function sorted(str1, str2) {
  str1 = [...str1].sort();
  str2 = [...str2].sort();
  let s1 = 0;
  let s2 = 0;
  while (s1 < str1.length && s2 < str2.length) {
    if(str1[s1] === str2[s2]) {
      s1 += 1;
    }
    s2 += 1;
  }
  return s1 === str1.length
}

对于未排序的项，最有效的解决方案是在最坏的情况下只遍历两个项目的字符：

function performant(str1, str2) {
  const stash = {};
  let s1 = 0;
  let s2 = 0;
  while (s1 < str1.length && s2 < str2.length) {
    const ch1 = str[s1];
    const ch2 = str[s2];
    if(ch1 === ch2) {
      s1 += 1;  
      s2 += 1; 
      continue;   
    }
    if (stash[ch1]) {
      s1 += 1; 
      stash[ch1] -= 1;
    }
    stash[ch2] = (stash[ch2] | 0) + 1;
    s2 += 1;
  }
  return s1 === str1.length;
}