727 - Minimum Window Subsequence
Written on February 3, 2020
Tweet
Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string “”. If there are multiple such minimum-length windows, return the one with the left-most starting index.
class Solution:
def minWindow(self, S: str, T: str) -> str:
dp = [[-1] * (len(S) + 1) for _ in range(len(T) + 1)]
#dp[i][j] starting index for T[i - 1] -> S[j - 1]
for j in range(len(S) + 1):
dp[0][j] = j
for i in range(1, len(T) + 1):
for j in range(1, len(S) + 1):
if T[i - 1] == S[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = dp[i][j - 1]
min_len = len(S) + 1
start = 0
for j, index in enumerate(dp[-1]):
if index != -1 and j - index < min_len: #j - 1 - index + 1
start = index
min_len = j - index
return S[start: start + min_len] if min_len <= len(S) else ""