javascript - 编写打乱函数的更简单方法

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

标签： javascript

Answer 1

此问题是检查一组元素是否是另一组元素的子集的通用问题的一个版本。

解决此任务的基本步骤是获取第一个元素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;
}