Python, O(m) space complexity, almost O(n) time complexity


  • 2
    S

    Very brief explannation : m = len(T), n = len(S), scan string S and maintain a up to date list of start index of matching T in list dp(size of m), dp[i] denotes the start index when i+1 chars of T are matched. When T[i] appears in S, we simply update dp[i] = dp[i-1], when T[0] appears in S with index, we update dp[0] = index. Whenever dp[m-1] is updated, we have a new window that T is sub-sequence of, and we keep a running minimum of this window width

    We scan S once, and each update depends the number of same char in T. The worst case is O(mn) when all position of T are identical. When the char in T doesn't have much repetition, O(n) time complexity is achieved.

    Space complexity O(m)

    class Solution(object):
        def minWindow(self, S, T):
            """
            :type S: str
            :type T: str
            :rtype: str
            """
            n = len(S)
            m = len(T)
            
            dic = dict()
            for i, s in enumerate(T):
                dic.setdefault(s, []).append(i)
                
            dp = [-1 for i in xrange(m)]
            
            count = n+1
            start = -1
            
            for index, c in enumerate(S):
                if c in dic:
                    for i in dic[c][::-1]:
                        if i == 0:
                            dp[i] = index
                        else:
                            dp[i] = dp[i-1]
                        if i == m-1 and dp[i] >= 0 and index - dp[i]+1 < count:
                            count = index - dp[i] + 1
                            start = dp[i]
            if dp[-1] < 0:
                return ""
            return S[start:start+count]
    

  • 0
    I

    java ver: 33ms, 97%

            int n = S.length(), m = T.length();
            Map<Character, List<Integer>> c2is = new HashMap<>();
            for (int i = 0; i < m; ++i) {
                List<Integer> is = c2is.getOrDefault(T.charAt(i), new ArrayList<>());
                is.add(i);
                c2is.put(T.charAt(i), is);
            }
            int[] dp = new int[m];
            Arrays.fill(dp, -1);
            int count = n + 1, start = -1;
            for (int i = 0; i < n; ++i) {
                char c = S.charAt(i);
                List<Integer> is = c2is.get(c);
                if (is == null) continue;
                for (int j = is.size() - 1; j >= 0; --j) {
                    int k = is.get(j);
                    dp[k] = k == 0 ? i : dp[k - 1];
                    if (k == m - 1 && dp[k] >= 0 && i - dp[k] + 1 < count) {
                        count = i - dp[k] + 1;
                        start = dp[k];
                    }
                }
            }
            return start < 0 ? "" : S.substring(start, start + count);
    

Log in to reply
 

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