Share my C++ O(ST) solution(not DP)


  • 1
    L
    class Solution {
    public:
        string minWindow(string S, string T)
        {
            int lenS = S.size();
            int lenT = T.size();
            vector<vector<int>> record(lenT, vector<int>());
            for (int i = 0; i < lenS; ++i)
                for (int j = 0; j < lenT; ++j)
                    if (S[i] == T[j])
                        record[j].push_back(i);
            vector<int> pos(lenT, 0);
            int minlen = INT_MAX;
            string ans;
            for (int i = 0; i < record[0].size(); ++i)
            {
                pos[0] = i;
                for (int j = 1; j < lenT; ++j)
                {
                    while (pos[j] < record[j].size() && record[j][pos[j]] <= record[j - 1][pos[j - 1]])
                        ++pos[j];
                    if (pos[j] == record[j].size())
                        return ans;
                }
                int temp = record[lenT - 1][pos[lenT - 1]] - record[0][pos[0]] + 1;
                if (i == 0)
                {
                    minlen = temp;
                    ans = S.substr(record[0][0], minlen);
                }
                else
                {
                    if (temp < minlen)
                    {
                        minlen = temp;
                        ans = S.substr(record[0][pos[0]], minlen);
                    }
                }
            }
            return ans;
        }
    };
    

  • 0
    S

    @linyacool Genius solution! Thanks a lot for sharing!


Log in to reply
 

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