題目網址：https://leetcode.cn/problems/minimum-window-subsequence/

題意：給兩 string s1、s2, 找出 s1 中最短的連續 substring w, 使得 s2 是 w 的 subsequence。

如果 s1 中沒有 window 可以包含 s2 中的所有 char, 則返回 ""。如果有不只一個最短長度的窗口, 則返回開始位置最靠左的那個。

注意：s1、s2 皆只由小寫英文所組成。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 s1、s2 前先加上一個 #, 代表什麼元素都沒有的狀態
  • dp[i][j]：以 s[i] 為結尾, 用 s1[1:i]、s2[1:j] 的 Minimum Window Subsequence 之長度

2. 得到轉移方程：

令 s1[1:i] = XXXXi, s2[1:j] = YYYj

  • 若 s1[i] == s2[j], 則 [XXXX]、[YYY] 建構的 substring 加上 s1[i] 即可
    ➔ dp[i][j] = dp[i - 1][j - 1] + 1
  • 否則, [XXXX]、[YYYj] 建構的 substring 加上 s1[i] 即可
    ➔ dp[i][j] = dp[i - 1][j] + 1

3. 初始化：

  • dp[0][0]：兩個 empty string "" 之 Minimum Window Subsequence 是 ""
    ➔ dp[0][0] = 0
  • dp[i][0]：s1[1:i]、"" 的 Minimum Window Subsequence 永遠是 ""
    ➔ dp[i][0] = 0, 其中 1 ≤ i ≤ m
  • dp[0][j]：s1[1:i] = ""、s2[1:j] 之 Minimum Window Subsequence 設為 INT_MAX / 2, 代表 s1[1:j] 不存在包含 s2[1:j] 之 substring。之所以不設成 INT_MAX 是因為這樣後續計算 dp[i][j] 時會 overflow
    ➔ dp[0][j] = INT_MAX / 2, 其中 1 ≤ j ≤ n

4. 注意事項：

  • 做完後, 找出所有 dp[i][n] 中最小的 i。如此一來, 就取得了 substring 結尾的 idx i 和長度 dp[i][n]
    ➔ 從而倒推出 substring 的起始 idx i - dp[i][n] + 1
  • 由於可能 s1 沒有 window 可以包含 s2 中的所有 char。但在狀態轉移方程中, 我們在 s1[i] != s2[j] 時, 仍直接把 s1[i] 加入到 window 中, 且 dp[0][j] 之初始值為 INT_MAX
    ➔ 因此我們最後要檢查最短窗口的長度是否 ≥ INT_MAX。若是的話, 代表 s1 中不存在包含 s2 的 window
class Solution {
public:
    string minWindow(string s1, string s2) {
        const int m = s1.size(), n = s2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        s1 = '#' + s1;
        s2 = '#' + s2;

        for (int i = 1; i <= m; ++i) {
            dp[i][0] = 0;
        }

        for (int j = 1; j <= n; ++j) {
            dp[0][j] = INT_MAX / 2;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + 1;
                }
            }
        }

        int len = INT_MAX / 2, end;
        for (int i = 1; i <= m; ++i) {
            if (dp[i][n] < len) {
                len = dp[i][n];
                end = i;
            }
        }

        return (len >= INT_MAX / 2) ? "" : s1.substr(end - len + 1, len);
    }
};
  • time：$O(m \cdot n)$ ➔ for loop
  • space：$O(m \cdot n)$ ➔ dp