Java DP 92ms solution O(S * T), only O(T.length) space


  • 0
    I

    Let me know if anyone needs explanation.

            public String minWindow(String S, String T) {
                int ls = S.length();
                int lt = T.length();
                int[] dp = new int[lt]; // max idx of T.charAt(i) so far
                Arrays.fill(dp, -1);
    
                String res = "";
    
                for (int i = 0; i < ls; i++) {
                    char cs = S.charAt(i);
                    for (int j = lt - 1; j >= 0; j--) { // go backward so we don't override previous iteration's result, e.g. when T = "bb"
                        if (cs == T.charAt(j)) {
                            if (j == 0) dp[j] = i;
                            else dp[j] = dp[j-1];
    
                            if (j == lt - 1) {
                                if (j == 0) return T;
                                if (dp[j - 1] != -1) {
                                    String newRes = S.substring(dp[j - 1], i + 1);
                                    if ("".equals(res) || newRes.length() < res.length()) res = newRes;
                                }
                            }
                        }
                    }
                }
    
                return res;
            }
    

Log in to reply
 

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