392_IsSubsequence - a920604a/leetcode GitHub Wiki

class Solution {
public:
    bool isSubsequence(string s, string t) {
        
        int n = t.size(), m = s.size(), j=0;
        if(n<m) return false;
        for(int i=0;i<n;++i){
            if(t[i] == s[j]) j++;
        }
        return j==m;
    }
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1,0));
        //      a   h   b   g   d   c   
        //  0   0   0   0   0   0   0
        //a 0   1   1   1   1   1   1
        //b 0   1   1   2   2   2   2
        //c 0   1   1   2   2   2   3
        
        for(int i=1;i<n+1;++i){
            for(int j=1;j<m+1;++j){
                if(s[i-1] == t[j-1]) dp[i][j] = 1+dp[i-1][j-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m]==s.size();
    }
};

class Solution {
public:
    int left_bound(vector<int> &nums, int target){
        int l = 0, r = nums.size();
        while(l<r){
            int mid = l + (r-l)/2;
            if(nums[mid] == target) r = mid;
            else if(nums[mid] > target) r= mid;
            else l = mid+1;
        }
        return l;
    }
    bool isSubsequence(string s, string t) {
        unordered_map<char, vector<int>> mp;
        int n = t.size();
        for(int i=0;i<n;++i){
            char c = t[i];
            if(mp.find(c)==mp.end()){
                mp[c].push_back(i);
            }
            else{
                mp[c].push_back(i);
            }
        }        
        int j =0; // index of t
        for(int i=0;i<s.size();++i){
            char c = s[i];
            // t 字串找不到 s[i] 這字元
            if(mp.find(c)==mp.end()) return false;
            int pos = left_bound(mp[c], j);
            // 二元搜尋區間中沒有字元 c
            if(pos == mp[c].size() )  return false;
            j = mp[c][pos]+1;
        }      
        return true;
    }
};