Hi there. I am having difficulty understanding the extra dp[i%2][j] = 0; operation in the improved version where the dp array only takes O(n).
I did the same way but just missing this statement and I cannot past all the tests. I am confused what does this statement do and why it is necessary?
Hi Roger and everyone that has the same question,
This is my understanding of the optimized tabulated solution. In the initial solution, our space complexity was m*n (the shape of the table when we place string1 and string 2 against each other). However, when computing the results, the farthest back we go to obtain a previously computed result is 1 row. This is when both letter match. With this in mind, we can conclude we only need to carry around 2 rows worth of space. % 2 will help us with that. In case you’re coming from a different language please be mindful that % in Javascript is a remainder operator, not modulo (https://2ality.com/2019/08/remainder-vs-modulo.html).
2 % 2 = 0
3 % 2 = 1
4 % 2 = 0
5 % 2 = 1
6 % 2 = 0
7 % 2 = 1
What we see is when we modulo by 2, we can only get 0 or 1 as a result and we can use this to determine which of the two rows we want to land on, and we refer to the previous row with by moving back 1 from the index we’re on.
dp[(i - 1) % 2]
Hope this helps!