C++ non-DP solution, O(MNln(M))


  • 0
    H

    Straight forward thought process:

    1. Build map to store the position(s) each char of T have appeared at in S
    2. Find the shortest increasing sequence S of positions in the map, such that S[0] is in map[T[0]], S[1] is in map[T[1]], ... S[N-1] is in map[T[N-1]], where N is T.size().

    Not sure if I got the big O correct. Comments?

        string minWindow(string S, string T) {
            unordered_map<int, vector<int>> locations;
            unordered_set<char> myset;
            for (auto c : T) {
                myset.insert(c);            
            }
            for (int i = 0; i < S.size(); i++) {
                if (myset.count(S[i])) {
                    locations[S[i]].push_back(i);
                }
            }
            
            int start = 0, len = INT_MAX;
            
            for (int i = 0; i < locations[T[0]].size(); i++) {
                size_t pos = locations[T[0]][i];
                int iter = 1;
                for (; iter < T.size(); iter++){
                    if (pos + 1 > locations[T[iter]].back()) 
                        break;
                    else{ 
                        pos = *lower_bound(locations[T[iter]].begin(), locations[T[iter]].end(), pos+1);
                    }
                }
                if (iter != T.size()) 
                    continue;
                if (pos - locations[T[0]][i] + 1 < len) {
                    len = pos - locations[T[0]][i] + 1;
                    start = locations[T[0]][i];
                }
            }
            if (len < INT_MAX)
                return S.substr(start, len);
            else
                return "";
        }
    

Log in to reply
 

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