DP C++ solution with detailed explanation - good for beginners


  • 0
    S

    The pattern of this problem is similar to a DP state problem. Here the states are:S[k] : Matched characters till index k in T.The dp variable holds the length of sequence matched in the current state. At each step of dp we loop through all characters in T checking for a match, if we dont match a character we increment the dp count, if we do match we take the result from index k-1 at previous step and increment

    An example should hopefully things more clear Suppose S : t1xxt2xt1t3t2t3 && T: t1t2t3

    dp[t1] dp[t2] dp[t3]
    t1 1 0 0
    x 2 0 0
    x 3 0 0
    t2 3 4 0
    x 4 5 0
    t1 1 6 0
    t3 2 7 7
    t2 3 3 0
    t3 4 4 4

    Hence the answer is 4 ending at index corresponding to last t3. There is a subtle point which makes the dp solution work which is : if we reach some intermediate state k at step i it is going to better or equivalent to current state k(ie youngest to reach is better). This is easy to see for the first character, but requires for some thinking for others. Imagine we have t1xxxt2xxt2 the second t2 is equivalent to t2 at this point wrt to the dp. Another example is t1xxxt2t1t2 - here we can see that the last t2 is actually optimal since it is reached by taking a newer t1. This is why the dp[i][j] = dp[i-1][j-1]+1 equation works and we don't need to check the edge from dp[i-1][j] (ie the old value) when reaching state j.

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

Log in to reply
 

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