C++, DP, O(S*T)


  • 0
    M

    I use dp[i + 1][j + 1] (0<=i<=T, 0<=j<=S) to represent the first index of W, so that S[dp[i + 1][j + 1], j] will be a valid W for S and T[0, i].

    class Solution {
    public:
        string minWindow(string S, string T) {
            int NS = S.size(), NT = T.size();
            vector<vector<int>> dp(NT + 1, vector<int>(NS + 1, -1));
            for (int i = 0; i < NS; ++i)
                dp[0][i] = i;
            for (int i = 0; i < NT; ++i)
            {
                for (int j = 0; j < NS; ++j)
                {
                    if (S[j] == T[i])
                    {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    else
                    {
                        dp[i + 1][j + 1] = dp[i + 1][j];
                    }
                }
            }
            string res = S + S;
            for (int i = 0; i < NS; ++i)
            {
                if (dp[NT][i + 1] != -1 && i - dp[NT][i + 1] + 1 < res.size())
                    res = S.substr(dp[NT][i + 1], i - dp[NT][i + 1] + 1);
            }
            return (res == S + S) ? "" : res;
        }
    };
    

Log in to reply
 

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