# leetcode: interleaving string

The description is here. The moment you see there are overlapping sub problems and sub optimal structure you know the problem can be solved easily using **dynamical programming**. The basic idea is thus:

the value of dp[i][j] represents if there is any of the interleaved strings come out of s1[0-i] and s2[0-j].

dp[i][j] = (dp[i-1][j] if s1[i] == s3[i+j]) or (dp[i][j-1] if s2[j] == s3[i+j])

for the sake of making programming easily, the matrix has been augmented by 1 in each dimension.

1 | class Solution { |

The above uses O(m*n) space, which is common case. We can reduce the space usage by **the observation** that to calculate dp[i][j] we only need to know dp[i-1][j] which is the value of last line above it and dp[i][j-1] which is the previous value of the same line.

So here I use array dp to represent both the values of the last line and the previous one. the trick is that when we calculating dp[j], dp[j-1] will store the previous value of the same line, and dp[j] itself (before write new value into it) is the value of last line above. Then we can use these two values to write new value into dp[j].

1 | class Solution { |