C++, AC, 16ms, O(1) space, not DP


  • 2
    W

    I thought my solution might be wrong, or at least TLE. I was a little surprised when it was accepted. I am thinking whether someone can design a case that makes this solution failed/TLE or give some complexity analysis.

    The idea is very straightforward:

    1. search T starting at S[p1] forwardly, and suppose it ends at S[p2];
    2. search T starting at S[p2] backwardly, and suppose it ends at S[p3];
    3. S[p3:p2] is then a possible answer;
    4. record the shortest answer and go to step 1 with p1 = p3 + 1.

    Code:

    class Solution {
    public:
        string minWindow(string S, string T) {
        string out;
        size_t p1 = 0;
    
        while (p1 + T.size() < S.size()) {
            size_t p2 = p1;
            bool isEnd = false;
            // forward search
            for (size_t i = 0; i < T.size(); i++) {
                while (S[p2] != T[i] && p2 < S.size()) {
                    p2++;
                }
                if (p2 == S.size()) {
                    isEnd = true;
                    break;
                }
                p2++;
            }
            if (isEnd)
                break;
            size_t p3 = --p2;
            // backward search
            for (int i = T.size() - 1; i >= 0; i--) {
                while (S[p3] != T[i]) {
                    p3--;
                }
                p3--;
            }
            p3++;
            // record the shortest answer
            if (out.empty())
                out = S.substr(p3, p2 - p3 + 1);
            else
                out = out.size() > (p2 - p3 + 1) ? S.substr(p3, p2 - p3 + 1) : out;
    
            p1 = p3 + 1;
        }
    
        return out;
        }
    };
    

  • 0
    M

    I have the same thought and I was confused by how to measure the time complexity of this algorithm. However, I don't think the answer is incorrect.


Log in to reply
 

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