Short Python DP solution, O(ST) time, O(T) space


  • 0
    Y

    The idea is to propagate the start index in S that matches the first char of T, and if S[i - 1] == T[j - 1], propagate the start index, otherwise keep the same start index since the new char in S is not used.

    class Solution:
        def minWindow(self, S, T):
            """
            :type S: str
            :type T: str
            :rtype: str
            """
            n, m = len(S), len(T)
            dp = [-1] * (m + 1)
            dp[0] = 0
            ret = ''
            for i in range(1, n + 1):
                for j in range(m, 0, -1):
                    if S[i - 1] == T[j - 1]:
                        dp[j] = dp[j - 1]
                dp[0] = i
                if dp[m] >= 0 and (not ret or i - dp[m] < len(ret)):
                    ret = S[dp[m]: i]
            return ret
    

Log in to reply
 

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