[727. Minimum Window Subsequence] C++ AC


  • 0

    Use the start index in the S as an indicator.

     class Solution {
     public:
     string minWindow(string S, string T) {
        if(S.empty() || T.empty()) return "";
        vector<int> info(S.size(), -1);
        for(int i = 0; i < info.size(); ++i){
            if(T[0] == S[i]) info[i] = i;
        }
        for(int t = 1; t < T.size(); ++t){
            vector<int> temp(S.size(), -1);
            int cur_start_index = -1;
            for(int s = 0; s < S.size(); ++s){
                if(S[s] == T[t] && cur_start_index >= 0){
                    temp[s] = cur_start_index;
                }
                if(info[s] >= 0) cur_start_index = info[s];//update the start index information
            }
            info = temp;
        }
        int cur_min_len = INT_MAX;
        int cur_s = 0;
        int cur_e = 0;
        for(int i = 0; i < info.size(); ++i){
            if(info[i] != -1){
                if(cur_min_len > i - info[i] + 1){
                    cur_min_len = i - info[i] + 1;
                    cur_s = info[i];
                    cur_e = i;
                }
            }
        }
        return cur_min_len == INT_MAX ? "" : S.substr(cur_s, cur_min_len);
     }
     };

Log in to reply
 

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