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


  • 4
    E
    class Solution {
    public:
        string minWindow(string s, string t) {
            int ns = s.size(), nt= t.size();
            int dp[ns+1][nt+1] = {};
            const int mxx = ns + 1;
            for (int i = 0 ; i <= ns; ++i) {
                for (int j = 1; j <= nt; ++j) {
                    dp[i][j] = mxx;
                    if (i) {
                        dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]);
                        if (s[i-1] == t[j-1]) dp[i][j]  = min(dp[i][j], 1 + dp[i-1][j-1]);
                    }
                }
            }
            
            int ans = ns + 1, x = -1;
            for (int i = 0; i <=ns; ++i) if (dp[i][nt] < ans) {
                x = i;
                ans = dp[i][nt];
            }
            
            if (x < 0) return "";
            return s.substr(x-ans,ans);
        }
    };
    

  • 0

    Hi @elastico thanks for sharing your solution. Could you please provide a brief explanation? I'm having a hard time following it, and unfortunately I don't get it. Thanks again, Clayton


  • 1

    @claytonjwong
    f[i][j] is the min length of w in S[0,...i - 1] (the first i char from S) that have subsequence T[0, ..., j - 1] (first j char from T). the statement dp[i][j] = min(dp[i][j], 1 + dp[i-1][j]); is the hardest part of this solution, the 1 means the char s[i - 1] (the last char of first i chars) is added. if S[i - 1] == T[j - 1], we update f[i][j].
    Taking this simple example:

    i = 1 2 3 4 5 6
    j---a b c d e a
    1 b 6 1 2 3 4 5 
    2 d 6 6 6 3 4 5
    3 e 6 6 6 6 4 5
    

Log in to reply
 

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