# Do we really need DP, BS?

• I was shocked by the tags of this problem. Then when I looked at it I found without using these fancy algorithms, there is a rather straight-forward solution with linear time complexity.

Maybe I'm wrong and I would appreciate it if someone can tell me how to reduce it into logN using DP or BS?

Below is my Java solution:

'''
public boolean isSubsequence(String s, String t) {

``````    if (t.length() == 0 && s.length() == 0) return true;
if (t.length() == 0) return false;
if (s.length() == 0) return true;

int target_index = 0;
for (int i = 0; i < t.length(); i ++) {
if (s.charAt(target_index) == t.charAt(i)) {
if (target_index == s.length()-1) return true;
target_index ++;
}
}
return false;
}
``````

'''

• Actually you do not need

if (t.length() == 0 && s.length() == 0) return true;
and
if (t.length() == 0) return false;

• yes, you are correct! thanks for pointing it out!

• Actually, we can solve this with Binary search if there are many incoming data.

``````class Solution {
public:
bool isSubsequence(string s, string t) {
//build a record to store the index of each char in t
vector<vector<int>> record(26);
for(int i = 0; i < t.size(); i++) {
record[t[i]-'a'].push_back(i);
}
//check if each char in s is in the legal place
int index = -1;
for(int i = 0; i < s.size(); i++) {
auto iter = upper_bound(record[s[i]-'a'].begin(), record[s[i]-'a'].end(), index);
if(iter == record[s[i]-'a'].end()) return false;
index = *iter;
}
return true;
}
};``````

• @xiekun2016
Nice solution.

If I am not wrong. The time for building the record is O(t), and the time for each search is O( s * log(t/26) ) on average, since each letter will appear t/26 times in string t on avg.

Yeah.. I understand the record only needs to be built once, but each search is still O(s* log(t/26)) on average, which is actually O(s*log(t)) Is this really the best answer we can have?

Thanks.

Yes you are right the time for each search is O(s*log(t)). But it's still better than O(t) when the size of s is relatively small and the size of t is extremely large.

• here is a DP solution. Since it will take O(n^2), it will get time limit exceed when you submit it.

'''
public class Solution {
public boolean isSubsequence(String s, String t) {

``````    String tmp = s;
s = t;
t = tmp;

if (s == null || s.length() == 0){
return t == null || t.length() == 0;
}

if (t == null || t.length() == 0){
return true;
}

int m = t.length();
int n = s.length();

boolean[][] dp = new boolean[m][n];

//initial first col
if (t.charAt(0) == s.charAt(0)){
dp[0][0] = true;
}

for (int i = 1 ; i < m ; i++){
dp[i][0] = false;
}

//initial first row
for (int i = 1 ; i < n ; i++){
dp[0][i] = dp[0][i-1] || (s.charAt(i) == t.charAt(0));
}

for (int i = 1 ; i < m ; i++){
for (int j = 1 ; j < n ; j++){
if (s.charAt(j) == t.charAt(i)){
dp[i][j] = (dp[i-1][j-1] || dp[i][j-1]);
//all others to be true and continue;
if (dp[i][j]){
for (int k = j + 1 ; k < n ; k++){
dp[i][k] = true;
}
continue;
}
}
}
}

return dp[m-1][n-1];
}
``````

}
'''

• @xiekun2016 easy to understand

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