# AC C++ solution

• general idea: obviously we'd think of trying dp. use dp[a][b] = loc to represent S[loc...a] contains T[0..b]. In order to caldulate dp[a][b], we need to check if any S[0..k] match T[0..b-1] for k in [0, a-1] and dp[a][b] value of the latest dp[k][b-1] (which means current matching start index in string S is most closed to a because we are trying to get the most shortest length match)
string minWindow(string S, string T) {
int m = S.size(), n = T.size();
int dp[m][n];
memset(dp, -1, sizeof(dp));

``````    for(int i = 0; i < m; i ++){
if (S[i] == T[0]){
dp[i][0] = i;
}
}

for(int i = 1; i < n; i ++){
for(int j = i; j < m; j ++){
dp[j][i] = -1;
if (S[j] == T[i]){
for(int k = j -1; k >= 0; k --){

if (dp[k][i-1] != -1){
dp[j][i] = dp[k][i-1];
break;
}
}
}
}
}

string res;
for(int i = 0; i < m; i ++){
if (dp[i][n-1] != -1){
int start = dp[i][n-1];
string candidate = S.substr(start, i - start + 1);
if (res.empty() || res.size() > candidate.size()){
res = candidate;
}
}
}
return res;
}``````

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