javascript - CodeWars/合并字符串检查器

Question

接下来的挑战是:

At a job interview, you are challenged to write an algorithm to check if a given string, s, can be formed from two other strings, part1 and part2. The restriction is that the characters in part1 and part2 are in the same order as in s. The interviewer gives you the following example and tells you to figure out the rest from the given test cases.

我做错了什么？为什么它还是失败了？

我写了 2 个不同的脚本，但都不适用于某些测试用例

function isMerge(s, part1, part2) {
    var sArr = s.split('');
    var part1Arr = part1.split('');
    var part2Arr = part2.split('');
    var tempArr = new Array(sArr.length);
    function compareArrays(arr1, arr2){
    var count = 0;
    for (var i = 0; i < arr1.length; i++) {
        if (arr1[i] !== arr2[i]) count++;
    }
    return (count == 0);
    }
    for (var i = 0; i < sArr.length; i++) {
        for (var j = 0; j < part1Arr.length; j++) {
            if (sArr[i] == part1Arr[j]) tempArr[i] = j;
        }
        for (var k = 0; k < part2Arr.length; k++) {
            if (sArr[i] == part2Arr[k]) tempArr[i] = k;
        }
    }
    alert(tempArr);
    var check = tempArr.slice();
    check.sort();
    alert(check);
    if (compareArrays(tempArr, check)) return true;
    else return false;
}
alert(isMerge('codewars', 'cdw', 'oears'));

function isMerge(s, part1, part2) {
    // create arrays of letters
    var sArr = s.split('');
    var part1Arr = part1.split('');
    var part2Arr = part2.split('');
    // create an associative array 'temp' (0:C, 1:O and so on)
    var temp = {};
    for (var k = 0; k < sArr.length; k++) {
      temp[k] = sArr[k];
    }
    // reverse an associative array 'temp' (now C:0, O:0 and so on)
    for (var key in temp) {
        var keyTemp = key;
        var keyValue = temp[key];
        key = keyValue;
        temp[key] = keyTemp;
    }
    // the function that compares arrays
    function compareArrays(arr1, arr2){
        var count = 0;
        for (var i = 0; i < arr1.length; i++) {
            if (arr1[i] !== arr2[i]) count++;
        }
        return (count == 0);
        }
    // sorting function
    function order(a, b) {
        var comparingA;
        var comparingB;
      for (var char in temp) {
          if (char == a) {
              comparingA = temp[char]; // comparingA is the number of 'a' in object 'temp'
          }
          if (char == b){
              comparingB = temp[char]; // comparingB is the number of 'b' in object 'temp'
          }
      }
        return (comparingA - comparingB);
    }
    // create copies of arrays
    var part1Sorted = part1Arr.slice();
    var part2Sorted = part2Arr.slice();
    // and sort that copies
    part1Sorted.sort(order);
    part2Sorted.sort(order);
    // If the array did not change after sorting, the order of the letters was correct
    if  (compareArrays(part1Sorted, part1Arr) && compareArrays(part2Sorted, part2Arr)) {
    // so now we can check is merge possible
    sArr = sArr.sort();
    var parts = part1Arr.concat(part2Arr);
    parts = parts.sort();
    var res = compareArrays(sArr, parts);
    return res;
    }
    return false;
}
alert(isMerge('codewars', 'code', 'wasr'));
alert(isMerge('codewars', 'oers', 'cdwa'));

我刚刚在第二个脚本中添加了注释

Answer 1

我发现很难理解您的代码试图做什么。如果您提供评论并解释您尝试实现的算法背后的想法，将会有所帮助。

下面是一个带注释的递归示例，它考虑指向第 1 部分和第 2 部分的指针 i 和 j 是否可以构成到该点为止的有效合并。

function isMerge(s, part1, part2) {
  // Merge is invalid if the parts' lengths don't add up to the string's
  if (part1.length + part2.length != s.length)
    return false;
    
  // Recursive function
  function g(i, j){
    // Base case: both pointers are exactly at the end of each part
    if (i == part1.length && j == part2.length)
      return true;
    
    // One of our pointers has extended beyond the part's length,
    // that couldn't be right
    if (i > part1.length || j > part2.length)
      return false;
    
    // Just part1 matches here so increment i
    if (part1[i] == s[i + j] && part2[j] != s[i + j])
      return g(i + 1, j);
      
    // Just part2 matches here so increment j
    else if (part1[i] != s[i + j] && part2[j] == s[i + j])
      return g(i, j + 1);
      
    // Both parts match here so try incrementing either pointer
    // to see if one of those solutions is correct
    else if (part1[i] == s[i + j] && part2[j] == s[i + j])
      return g(i + 1, j) || g(i, j + 1);
      
    // Neither part matches here
    return false;
  }
    
  // Call the recursive function
  return g(0,0);
}

console.log(isMerge('codewars', 'cdw', 'oears'));
console.log(isMerge('codecoda', 'coda', 'code'));
console.log(isMerge('codewars', 'oers', 'cdwa'));
console.log(isMerge('codewars', 'cdw', 'years'));

非常长的字符串的堆栈版本:

function isMerge2(s, part1, part2) {
  if (part1.length + part2.length != s.length)
    return false;
    
  let stack = [[0,0]];
  
  while (stack.length){
    [i, j] = stack.pop();
    
    if (i == part1.length && j == part2.length)
      return true;

    if (i > part1.length || j > part2.length)
      continue;
    
    if (part1[i] == s[i + j] && part2[j] != s[i + j])
      stack.push([i + 1, j]);
      
    else if (part1[i] != s[i + j] && part2[j] == s[i + j])
      stack.push([i, j + 1]);
      
    else if (part1[i] == s[i + j] && part2[j] == s[i + j]){
      stack.push([i + 1, j]);
      stack.push([i, j + 1]);
    }
  }
    
  return false;
}

function test(){
  let s = '';
  
  for (let i=0; i<1000000; i++)
    s += ['a','b','c','d','e','f','g'][~~(Math.random()*6)];
  
  let lr = {
    l: '',
    r: ''
  };
  
  for (let i=0; i<s.length; i++){
    let which = ['l', 'r'][~~(Math.random()*2)];
    
    lr[which] += s[i];
  }
  
  console.log(isMerge2(s,lr.l,lr.r));
}

test();