AC C++ solution


  • 0
    S

    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;
    }

Log in to reply
 

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