CodeWars/ Merged String Checker

Question

The challenge is next:

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?

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

You might want to provide the "following example" and the "given test cases", otherwise we're kind of shooting in the dark. — k_ssb, Apr 22 '18 at 01:53
you can iterate strings like arrays, no need to convert first. just take the result of an function call as result, not need to check and return explicit `true` or `false`, if the function returns these values. please use `console.log` instead of `alert`, it prevents of anoying clicking ok. — Nina Scholz, Apr 22 '18 at 08:46
Here are three examples that return a false negative with your newly commented code. These should return true: `"baeabb", "b", "baeab"`; `"bdab", "bdab", ""`; `"bfaef", "f", "bfae"`; I hope that helps! — גלעד ברקן, Apr 22 '18 at 09:24

score 2 · Answer 1 · edited Mar 14 '19 at 05:05

Recursive Call:

You could use a recursive approach by first checking the length of string and part strings and then by the length or by checking a character and by checking the rest of the given part strings.

function isMerge(s, part1, part2) {
    if (s.length !== part1.length + part2.length) {
        return false;
    }

    if (!s.length) {
        return true;
    }

    if (part1[0] === s[0] && isMerge(s.slice(1), part1.slice(1), part2)) {
        return true;
    }

    if (part2[0] === s[0] && isMerge(s.slice(1), part1, part2.slice(1))) {
        return true;
    }

    return false;
}

console.log(isMerge('codewars', 'cdw', 'oears'));  //  true
console.log(isMerge('codewars', 'oers', 'cdwa'));  //  true
console.log(isMerge('codecoda', 'coda', 'code'));  //  true
console.log(isMerge('baeabb', 'b', 'baeab'));      //  true
console.log(isMerge('bdab', 'bdab', ''));          //  true
console.log(isMerge('bfaef', 'f', 'bfae'));        //  true
console.log(isMerge('codewars', 'cdw', 'years'));  // false
console.log(isMerge('codewars', 'code', 'warss')); // false
console.log(isMerge('codewars', 'codes', 'wars')); // false
console.log(isMerge('', 'a', 'b'));                // false

.as-console-wrapper { max-height: 100% !important; top: 0; }

With a Stack instead of a Recursive Call:

function isMerge(s, part1, part2) {
    var stack = [[s, part1, part2]];

    if (s.length !== part1.length + part2.length) {
        return false;
    }

    while (stack.length) {
        [s, part1, part2] = stack.shift();

        if (!s.length) {
            return true;
        }

        if (part1[0] === s[0]) {
            stack.push([s.slice(1), part1.slice(1), part2]);
        }

        if (part2[0] === s[0]) {
            stack.push([s.slice(1), part1, part2.slice(1)]);
        }
    }
    return false;
}

console.log(isMerge('codewars', 'cdw', 'oears'));  //  true
console.log(isMerge('codewars', 'oers', 'cdwa'));  //  true
console.log(isMerge('codecoda', 'coda', 'code'));  //  true
console.log(isMerge('baeabb', 'b', 'baeab'));      //  true
console.log(isMerge('bdab', 'bdab', ''));          //  true
console.log(isMerge('bfaef', 'f', 'bfae'));        //  true
console.log(isMerge('codewars', 'cdw', 'years'));  // false
console.log(isMerge('codewars', 'code', 'warss')); // false
console.log(isMerge('codewars', 'codes', 'wars')); // false
console.log(isMerge('', 'a', 'b'));                // false

.as-console-wrapper { max-height: 100% !important; top: 0; }

Seems to fail with these (they should all return false): `isMerge('codewars', 'code', 'warss');` `isMerge('codewars', 'codes', 'wars');` `isMerge('', 'a', 'b');` — גלעד ברקן, Apr 22 '18 at 00:59
it passes all the tests, but it seems to me that the solution may be easier — Skywrath, Apr 22 '18 at 07:54
This works but throws a `RangeError: Maximum call stack size exceeded` for a string of 8,000 characters. See here: https://repl.it/@gl_dbrqn/PlayfulNastyPayware Mine does too at about 11,000 :) I guess they could both be more efficient with stack or table. — גלעד ברקן, Apr 22 '18 at 09:48
Stack is cool but I think you might have a bug. It locks the browser for strings longer than around 300. You can see here which strings seem problematic: https://repl.it/@gl_dbrqn/PlayfulNastyPayware-1 — גלעד ברקן, Apr 22 '18 at 14:27

גלעד ברקן · Answer 2 · 2018-04-22T15:11:19.233

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.

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

Nick · Answer 3 · 2018-04-22T22:35:22.843

1

This is a recursive approach: it checks for a match of the first character of the string with either of the parts, and if there's a match recurses to try and match the rest of the string with the rest of the parts. The tricky thing is that when the first character of both parts is the same, you have to check if you can match against either of them (this solves the Bananas test).

function isMerge(str, p1, p2) {
  if (!str.length) return !p1.length && !p2.length;
  if (p1.length && str.charAt(0) == p1.charAt(0)) {
    if (p2.length && str.charAt(0) == p2.charAt(0)) {
      return isMerge(str.substr(1), p1.substr(1), p2) || isMerge(str.substr(1), p1, p2.substr(1));
    }
    else {
      return isMerge(str.substr(1), p1.substr(1), p2);
    }
  }
  else if (p2.length && str.charAt(0) == p2.charAt(0)) {
    return isMerge(str.substr(1), p1, p2.substr(1));
  }
  else {
    return false;
  }
}

edited Apr 22 '18 at 22:35

answered Apr 21 '18 at 23:06

Nick

138,499
22
57
95

This code seems to fail some of the test cases. It's easy to sign up and try :) – גלעד ברקן Apr 22 '18 at 02:34
Which test cases? @גלעדברקן – Nick Apr 22 '18 at 02:35
Here's the link (sign in and click on "train"): https://www.codewars.com/kata/merged-string-checker – גלעד ברקן Apr 22 '18 at 02:39
Thanks for the link. I got a clue from one of the test names as to where my mistake was. This new code gets 76 of 76 @גלעדברקן – Nick Apr 22 '18 at 03:41

Antonio Pangallo · Answer 4 · 2018-04-21T22:04:19.113

0

May you try this below?

function isMerge(s, part1, part2) { 
  var result= true;
  var total = part1 + part2; 
  for (var i = 0; i < s.length; i++) { 
    var char = s.charAt(i); 
    if(total.indexOf(char) === -1) {
      result = false;
      break;
    } 
  } 
  return result;
}

edited Apr 21 '18 at 22:04

answered Apr 21 '18 at 21:57

Antonio Pangallo

220
2
5

Passed: 71 Failed: 5 Errors: 1 – Skywrath Apr 21 '18 at 22:18

score 0 · Answer 5 · answered Apr 21 '18 at 22:09

First of all, here is your code just working:

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] = part1Arr[j];
    }
    for (var k = 0; k < part2Arr.length; k++) {
        if (sArr[i] == part2Arr[k]) tempArr[i] = part2Arr[k];
    }
}
alert(tempArr);

 if (compareArrays(tempArr, sArr)) return true;
 else return false;
}
alert(isMerge('codewars', 'cdw', 'oears'));

Now, what was the problem?

for (var j = 0; j < part1Arr.length; j++) {

                /* Here you assigned the index (tempArr[i] = j;) not the char */
     if (sArr[i] == part1Arr[j]) tempArr[i] = part1Arr[j];
}

for (var k = 0; k < part2Arr.length; k++) {

                /* Here you assigned the index (tempArr[i] = k;) not the char */
     if (sArr[i] == part2Arr[k]) tempArr[i] = part2Arr[k];
}

Hope i could help you ;)

still fails Passed: 71 Failed: 5 Errors: 1 – Skywrath Apr 21 '18 at 22:23 — Skywrath, Apr 21 '18 at 22:23

score 0 · Answer 6 · answered Apr 22 '18 at 03:22

Simple merge logic:

function isMerge(s, part1, part2) {
    var sArr = s.split('');
    var part1Arr = part1.split('');
    var part2Arr = part2.split('');
    
    var j = 0;
    var k = 0;
    for (var i = 0; i < sArr.length; i++) {
        if ((j < part1Arr.length) && (sArr[i] == part1Arr[j]))
          j++
        else if ((k < part2Arr.length) && (sArr[i] == part2Arr[k])) 
          k++
        else 
          break
    }
    return (j == part1Arr.length && k == part2Arr.length && (j + k) == sArr.length);
}

console.log(isMerge('abcd', 'ac', 'bd'));
console.log(isMerge('abcd', 'acd', 'b'));
console.log(isMerge('abcd', 'ac', 'b'));
console.log(isMerge('abcd', 'ac', 'db'));
console.log(isMerge('abcd', 'c', 'b'));
console.log(isMerge('a', '', 'a'));
console.log(isMerge('', '', ''));
console.log(isMerge('', 'a', 'b'));
console.log(isMerge('ab', '', ''));

`Passed: 54 Failed: 22 Errors: 1` :) https://www.codewars.com/kata/merged-string-checker/train/javascript — גלעד ברקן, Apr 22 '18 at 03:47
@גלעד ברקן I began to make table filling approach (like non-recursive equivalent of yours) but erroneously decided that simple forward moving has no counterexamples. Thanks for checker link — MBo, Apr 22 '18 at 05:09

CodeWars/ Merged String Checker

6 Answers6

Recursive Call:

With a Stack instead of a Recursive Call:

Linked