MyC++CodeforLeetCodeOJ.zip资源-CSDN文库

共2000个文件

md：2000个

需积分: 5 139 浏览量 2023-12-31 11:12:58 上传评论收藏 11.34MB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

My C++ Code for LeetCode OJ.zip （2000个子文件）

README.md 98KB

README.md 66KB

README.md 32KB

README.md 18KB

README.md 17KB

README.md 14KB

README.md 12KB

README.md 11KB

README.md 10KB

README.md 9KB

README.md 8KB

README.md 7KB

共 2000 条

# [727. Minimum Window Subsequence (Hard)](https://leetcode.com/problems/minimum-window-subsequence) Given strings <code>s1</code> and <code>s2</code>, return the minimum contiguous substring part of <code>s1</code>, so that <code>s2</code> is a subsequence of the part. If there is no such window in <code>s1</code> that covers all characters in <code>s2</code>, return the empty string <code>""</code>. If there are multiple such minimum-length windows, return the one with the left-most starting index.   Example 1: <pre>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. </pre> Example 2: <pre>Input: s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u" Output: "" </pre>   Constraints: <ul> <li><code>1 <= s1.length <= 2 * 104</code></li> <li><code>1 <= s2.length <= 100</code></li> <li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li> </ul> **Companies**: [Google](https://leetcode.com/company/google), [Snapchat](https://leetcode.com/company/snapchat), [eBay](https://leetcode.com/company/ebay) **Related Topics**: [String](https://leetcode.com/tag/string/), [Dynamic Programming](https://leetcode.com/tag/dynamic-programming/), [Sliding Window](https://leetcode.com/tag/sliding-window/) **Similar Questions**: * [Minimum Window Substring (Hard)](https://leetcode.com/problems/minimum-window-substring/) * [Longest Continuous Increasing Subsequence (Easy)](https://leetcode.com/problems/longest-continuous-increasing-subsequence/) ## Solution 1. DP Let `dp[i+1][j+1]` be the number of matched letters between `s[0..i]` and `t[0..j]`, `start[i+1][j+1]` be the starting index of the minimum window corresponding to `dp[i+1][j+1]`. Initially `dp[i+1][j+1] = 0`, `start[i+1][j+1] = -1`. If `s[i] == t[j]`, `dp[i+1][j+1] = 1 + dp[i][j]`. `start[i+1][j+1] = j == 0 ? i : start[i][j]`. If `s[i] != t[j]`, `dp[i+1][j+1] = max(dp[i][j+1], dp[i][j])`. If `dp[i+1][j+1] == dp[i][j+1]`, `start[i+1][j+1] = start[i][j + 1]`. Additionally, if `dp[i+1][j+1] = dp[i][j]`, `start[i+1][j+1] = max(start[i+1][j+1], start[i][j])` ```cpp // OJ: https://leetcode.com/problems/minimum-window-subsequence // Author: github.com/lzl124631x // Time: O(MN) // Space: O(MN) class Solution { public: string minWindow(string s, string t) { int M = s.size(), N = t.size(); vector<vector<int>> dp(M + 1, vector<int>(N + 1)), start(M + 1, vector<int>(N + 1, -1)); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (s[i] == t[j]) { dp[i + 1][j + 1] = 1 + dp[i][j]; if (j == 0) { start[i + 1][j + 1] = i; } else { start[i + 1][j + 1] = start[i][j]; } } else { dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i][j]); if (dp[i + 1][j + 1] == dp[i][j + 1]) { start[i + 1][j + 1] = start[i][j + 1]; } if (dp[i + 1][j + 1] == dp[i][j]) { start[i + 1][j + 1] = max(start[i + 1][j + 1], start[i][j]); } } } } int minLen = INT_MAX, st = -1; for (int i = 0; i < M; ++i) { if (dp[i + 1][N] == N && i - start[i + 1][N] + 1 < minLen) { st = start[i + 1][N]; minLen = i - start[i + 1][N] + 1; } } return minLen == INT_MAX ? "" : s.substr(st, minLen); } }; ``` Since `dp[i + 1][j + 1]` only depends on `dp[i][j]` and `dp[i + 1][j]`, we can reduce the space complexity from `O(MN)` to `O(N)`. ```cpp // OJ: https://leetcode.com/problems/minimum-window-subsequence // Author: github.com/lzl124631x // Time: O(MN) // Space: O(N) class Solution { public: string minWindow(string s, string t) { int M = s.size(), N = t.size(), minLen = INT_MAX, st = -1; vector<int> dp(N + 1), start(N + 1, -1); for (int i = 0; i < M; ++i) { for (int j = N - 1; j >= 0; --j) { if (s[i] == t[j]) { dp[j + 1] = 1 + dp[j]; start[j + 1] = j == 0 ? i : start[j]; } else { dp[j + 1] = max(dp[j + 1], dp[j]); if (dp[j + 1] == dp[j]) start[j + 1] = max(start[j + 1], start[j]); } } if (dp[N] == N && i - start[N] + 1 < minLen) { st = start[N]; minLen = i - start[N] + 1; } } return minLen == INT_MAX ? "" : s.substr(st, minLen); } }; ``` ## Solution 2. Greedy <h4 id="intuition-2">Intuition</h4> Let <code>start</code> and <code>end</code> denote the left-most and right-most indices of a given window/substring in <code>s1</code>. We can try all possible values of <code>start</code>, and for each of them, find the smallest value of <code>end</code> such that <code>s2</code> is a subsequence of <code>s1[start..end]</code>. Let <code>m</code> denote the length of <code>s2</code>. We want to find a sequence of indices i0,i1,...,im−1i_0, i_1, ..., i_{m-1}i0,i1,...,im−1</

评论收藏

内容反馈