# AC straight forward solution and two DP solutions, MLE and TLE respectively

• I am new to `DP` and picked this problem to practice my `DP` skill, after I try my best to solve this problem with `DP` (I don't know if it is real `DP`) , I found that both of my solutions were not accepted, `MLE` and `TLE` respectively, here are my codes:

``````	/*
* Memory Limit Exceeded
*/
public boolean isSubsequence(String s, String t) {
if (s.length() == 0)
return true;
if (s.length() == t.length())
return s.equals(t);
if (s.length() > t.length())
return false;

boolean[][] result = new boolean[s.length()][t.length()];		// too many memory here
result[0][0] = s.charAt(0) == t.charAt(0);
for (int i = 1; i < t.length(); i++)
result[0][i] = result[0][i - 1] || s.charAt(0) == t.charAt(i);

for (int i = 1; i < s.length(); i++) {
for (int j = i + 1; j < t.length(); j++) {
result[i][j] = result[i][j - 1] || (result[i - 1][j - 1] && s.charAt(i) == t.charAt(j));
}
}
return result[s.length() - 1][t.length() - 1];
}

/*
* Time Limit Exceeded
*/
public boolean isSubsequenceV2(String s, String t) {
if (s.length() == 0)
return true;
return isSubsequenceHelper(s, s.length() - 1, t, t.length() - 1);
}

private boolean isSubsequenceHelper(String s, int index1, String t, int index2) {
if (index1 == 0)
return t.substring(0, index2 + 1).contains(s.substring(0, index1 + 1));
if (index1 > index2)
return false;
return isSubsequenceHelper(s, index1, t, index2 - 1)
|| (isSubsequenceHelper(s, index1 - 1, t, index2 - 1) && s.charAt(index1) == t.charAt(index2));		// too many recursion here
}

// linear solution
public boolean isSubsequenceV3(String s, String t) {
int indexOfS = 0;
int indexOfT = 0;
while (indexOfS < s.length() && indexOfT < t.length()) {
if (s.charAt(indexOfS) == t.charAt(indexOfT))
indexOfS++;
indexOfT++;
}
return indexOfS == s.length() && indexOfT < t.length();
}
``````

Anyone can point out that if I am use the real `DP` idea? Thanks in advance!!

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