# My DP solution, but got TLE in space. any idea.

• got TLE in space. anyone knows why?

``````
public boolean isSubsequence(String s, String t) {
int m=s.length();
int n=t.length();
boolean[][]dp=new boolean[m+1][n+1];
for(int i=0;i<n+1;i++){
dp[0][i]=true;
}
for(int i=0;i<m+1;i++){
dp[i][0]=false;
}
dp[0][0]=true;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dp[i+1][j+1]=(s.charAt(i)==t.charAt(j)&&dp[i][j])||dp[i+1][j];
}
}
return dp[m][n];
}
``````

• Same here. Got MLE with classical way of DP solution. Since here the (i, j) problem is only related to (i-1, j-1) or (i-1, j) problem, you can use a rolling array instead of a whole matrix. The trick is, you still define the dp matrix as you always did, except making the row length to be 2, and take a modulo of 2 when you update dp state. Also, use s's length as column length will help you, because the question says that t's length can be very large. So now the memory usage will only be two arrays of s's length.

``````public class Solution {
public boolean isSubsequence(String s, String t) {
// check edge case
if (s == null || t == null) {
return true;
}
// preprocess
int sLen = s.length();
int tLen = t.length();
// dp def
boolean[][] dp = new boolean[2][sLen + 1];
// dp init
dp[0][0] = true;
for (int j = 1; j <= sLen; j++) {
dp[0][j] = false;
}
// dp transition
for (int i = 1; i <= tLen; i++) {
for (int j = 0; j <= sLen; j++) {
if (j == 0) {
dp[i % 2][0] = true;
continue;
}
char tCh = t.charAt(i - 1);
char sCh = s.charAt(j - 1);
if (sCh == tCh) {
dp[i % 2][j] |= dp[(i-1) % 2][j-1];
}
dp[i % 2][j] |= dp[(i - 1) % 2][j];
}
}
return dp[tLen % 2][sLen];
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.