Python dp + binary search


  • 0
    D

    O(T*S*log(S))

    from collections import defaultdict
    from bisect import bisect_left
    class Solution:
        def minWindow(self, S, T):
            indices = defaultdict(list)
            for i in range(len(S)):
                indices[S[i]].append(i)
            
            dp = defaultdict(lambda: defaultdict(lambda: -1))
            
            ret = (len(S), len(S))
            for t in range(0, len(T)):
                for s in range(0, len(S)):
                    if T[t] == S[s]:
                        if t == 0:
                            dp[t][s] = s
                        else:
                            ids = indices[T[t-1]]
                            pos = bisect_left(ids, s) - 1
                            if pos >= 0:
                                dp[t][s] = dp[t-1][ids[pos]]
                        if dp[t][s] != -1 and t == len(T)-1:
                            ret = min(ret, (s+1 - dp[t][s], dp[t][s]))
            l, s = ret
            return S[s:s+l]      
    

    Another solution which is O(T*S) but apparently not fast enough

    class Solution:
        def minWindow(self, S, T):        
            dp = []
            for i in range(len(T)):
                dp.append([])
                for j in range(len(S)):
                    dp[-1].append(-1)
                    
            ret = (len(S), len(S))
            for t in range(0, len(T)):
                for s in range(0, len(S)):
                    if T[t] == S[s]:
                        if t == 0:
                            dp[t][s] = s
                        elif t>0 and s>0:
                            dp[t][s] = dp[t-1][s-1]
                        
                        if t == len(T)-1 and dp[t][s] != -1 :
                            ret = min(ret, (s+1 - dp[t][s], dp[t][s]))
                    elif s>0:
                        dp[t][s] = dp[t][s-1]
            l, s = ret
            return S[s:s+l] 
    

Log in to reply
 

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