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[i1][j]);
if (s[i1] == t[j1]) dp[i][j] = min(dp[i][j], 1 + dp[i1][j1]);
}
}
}
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(xans,ans);
}
};
C++ DP O(len(S)*len(T))


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

@claytonjwong
f[i][j]
is the min length ofw
inS[0,...i  1]
(the first i char from S) that have subsequenceT[0, ..., j  1]
(first j char from T). the statementdp[i][j] = min(dp[i][j], 1 + dp[i1][j]);
is the hardest part of this solution, the1
means the chars[i  1]
(the last char of first i chars) is added. ifS[i  1] == T[j  1]
, we updatef[i][j]
.
Taking this simple example:i = 1 2 3 4 5 6 ja 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