CodeWars/合并的字符串检查器 [英] CodeWars/ Merged String Checker

问题描述

接下来的挑战:

在工作面试中，您面临编写一个算法来检查给定字符串s是否可以由其他两个字符串part1和part2构成的挑战.限制是part1和part2中的字符与s中的顺序相同.面试官为您提供以下示例，并告诉您从给定的测试用例中找出其余的内容.

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.

我做错了什么?为什么仍然会失败?

What am I doing wrong? Why it fails anyway?

我写了2个不同的脚本，但都无法在某些测试用例中使用

I wrote 2 different scripts, and both aren't working for some test cases

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'));

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

I just added comments to the second script

推荐答案

我发现很难理解您的代码正在尝试执行的操作.如果您提供注释以及解释您尝试实现的算法背后的思想，那将有所帮助.

I find it hard to understand what your code is attempting to do. It would help if you provided comments as well as explain the idea behind the algorithm/s you are attempting to implement.

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

Here's a commented example of a recursion that considers if pointers i and j to parts 1 & 2 could constitute a valid merge up to that point.

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'));

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

Stack version for really long strings:

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();

这篇关于CodeWars/合并的字符串检查器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！