Do we really need DP, BS?


  • 6
    H

    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;
    }
    

    '''


  • 0
    W

    Actually you do not need

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


  • 0
    H

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


  • 14
    X

    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);
            //add indexs
            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;
        }
    };

  • 0

    @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.


  • 0
    X

    Thank your for your opinion.

    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.


  • 0
    W

    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];
    }
    

    }
    '''


  • 0
    Y

    @xiekun2016 easy to understand


Log in to reply
 

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