Question

727. Minimum Window Subsequence

中文文档

Description

Given strings s1 and s2, return _the minimum contiguous substring part of _s1_, so that _s2_ is a subsequence of the part_.

If there is no such window in s1 that covers all characters in s2, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index.

 

Example 1:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer because it occurs before "bdde" which has the same length.
"deb" is not a smaller window because the elements of s2 in the window must occur in order.

Example 2:

Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
Output: ""

 

Constraints:

• 1 <= s1.length <= 2 * 104
• 1 <= s2.length <= 100
• s1 and s2 consist of lowercase English letters.

Solutions

Solution 1

class Solution:
  def minWindow(self, s1: str, s2: str) -> str:
    m, n = len(s1), len(s2)
    f = [[0] * (n + 1) for _ in range(m + 1)]
    for i, a in enumerate(s1, 1):
      for j, b in enumerate(s2, 1):
        if a == b:
          f[i][j] = i if j == 1 else f[i - 1][j - 1]
        else:
          f[i][j] = f[i - 1][j]
    p, k = 0, m + 1
    for i, a in enumerate(s1, 1):
      if a == s2[n - 1] and f[i][n]:
        j = f[i][n] - 1
        if i - j < k:
          k = i - j
          p = j
    return "" if k > m else s1[p : p + k]

class Solution {
  public String minWindow(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] f = new int[m + 1][n + 1];
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
          f[i][j] = j == 1 ? i : f[i - 1][j - 1];
        } else {
          f[i][j] = f[i - 1][j];
        }
      }
    }
    int p = 0, k = m + 1;
    for (int i = 1; i <= m; ++i) {
      if (s1.charAt(i - 1) == s2.charAt(n - 1) && f[i][n] > 0) {
        int j = f[i][n] - 1;
        if (i - j < k) {
          k = i - j;
          p = j;
        }
      }
    }
    return k > m ? "" : s1.substring(p, p + k);
  }
}

class Solution {
public:
  string minWindow(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    int f[m + 1][n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        if (s1[i - 1] == s2[j - 1]) {
          f[i][j] = j == 1 ? i : f[i - 1][j - 1];
        } else {
          f[i][j] = f[i - 1][j];
        }
      }
    }
    int p = 0, k = m + 1;
    for (int i = 1; i <= m; ++i) {
      if (s1[i - 1] == s2[n - 1] && f[i][n]) {
        int j = f[i][n] - 1;
        if (i - j < k) {
          k = i - j;
          p = j;
        }
      }
    }
    return k > m ? "" : s1.substr(p, k);
  }
};

func minWindow(s1 string, s2 string) string {
  m, n := len(s1), len(s2)
  f := make([][]int, m+1)
  for i := range f {
    f[i] = make([]int, n+1)
  }
  for i := 1; i <= m; i++ {
    for j := 1; j <= n; j++ {
      if s1[i-1] == s2[j-1] {
        if j == 1 {
          f[i][j] = i
        } else {
          f[i][j] = f[i-1][j-1]
        }
      } else {
        f[i][j] = f[i-1][j]
      }
    }
  }
  p, k := 0, m+1
  for i := 1; i <= m; i++ {
    if s1[i-1] == s2[n-1] && f[i][n] > 0 {
      j := f[i][n] - 1
      if i-j < k {
        k = i - j
        p = j
      }
    }
  }
  if k > m {
    return ""
  }
  return s1[p : p+k]
}

function minWindow(s1: string, s2: string): string {
  const m = s1.length;
  const n = s2.length;
  const f: number[][] = Array(m + 1)
    .fill(0)
    .map(() => Array(n + 1).fill(0));
  for (let i = 1; i <= m; ++i) {
    for (let j = 1; j <= n; ++j) {
      if (s1[i - 1] === s2[j - 1]) {
        f[i][j] = j === 1 ? i : f[i - 1][j - 1];
      } else {
        f[i][j] = f[i - 1][j];
      }
    }
  }
  let p = 0;
  let k = m + 1;
  for (let i = 1; i <= m; ++i) {
    if (s1[i - 1] === s2[n - 1] && f[i][n]) {
      const j = f[i][n] - 1;
      if (i - j < k) {
        k = i - j;
        p = j;
      }
    }
  }
  return k > m ? '' : s1.slice(p, p + k);
}