0

I'm not quite sure why is this happening but here's the thing:

I'm trying to code the Longest common sub sequence problem but I'm getting this bug, where I try to add a new value to the matrix (NxM multidimension array) but the value is added to all the arrays in the same position.

Example: Adding 1 to matrx[1][1]

0100000
0100000
0100000
...
0100000

Here's the code

var input="XMJYAUZ;MZJAWXU";

var string=input.split(";");

var matrix=[];

for(var i=0;i<string[0].length+1;i++){

        matrix[i]=0;

}

var matrx=[];

for(var j=0;j<string[1].length+1;j++){

     matrx[j]=matrix;

}


matrx=buildMatrix(string[0][0],string[1][0],1,1);


function buildMatrix(A,B,x,y){

if (A != B){

    matrx[x][y]=Math.max(matrx[x-1][y],matrx[x][y-1]);

}
else{

    matrx[x][y]=matrx[x-1][y-1]+1;

}

//check x and y
if(x==string[0].length && y==string[1].length){

}
else if(y==string[1].length){

    buildMatrix(string[0][x],string[1][0],x+1,1);

}
else{
    buildMatrix(string[0][0],string[1][y],x,y+1);
}

return matrx;
}
CanIHazCookieNow
  • 112
  • 1
  • 10

1 Answers1

1

A problem here:

var matrx=[];

for(var j=0;j<string[1].length+1;j++){

     matrx[j]=matrix;

}

Is that you are adding the exact same array to every position. Thus, when you then add items to that array, it appears in all positions because all positions point to the exact same array. You need to add a different array to each position like this:

for(var j=0;j<string[1].length+1;j++){

     matrx[j] = [];

}

It may help to remember that arrays and objects are assigned by reference - javascript just assigns a pointer to the array or object - it does not make a copy. That means when you have something like this:

var a = [];
var b = a;

You now have both b and a pointing at the exact same array. If you then do this:

a.push(3);
console.log(a.length);    // shows 1
console.log(b.length);    // shows 1

You will see that both a and b show the same change because they point to the same array.

Some relevant references:

Pointer behavior between objects

Do objects pushed into an array in javascript deep or shallow copy?

is it possible in Javascript to tell an object to stop having reference behavior with another object

Javascript by reference vs. by value

Community
  • 1
  • 1
jfriend00
  • 683,504
  • 96
  • 985
  • 979
  • Thanks for the help. Working now. Just out of curiosity, why doesn't javascript makes a copy instead ? – CanIHazCookieNow Jan 24 '14 at 16:41
  • @Haltinpot - I wasn't there in the design meetings when they decided to do references for arrays and objects so I don't know the exact rationale. I would guess that much of the time you just want a reference so they needed to make a way to have a reference. And, you don't really want to go making copies of potentially really big things if a copy isn't explicitly needed. FYI, you can make your own shallow copy of an array at any time with `array.slice(0)`. – jfriend00 Jan 24 '14 at 17:01