原题：判断子序列

，维护一个技术count，只要一次遍历T，T[i] = S[count]，则计数+1，当计数长度和S相等，说明存在子串，直接返回。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    bool isSubsequence(string S, string T) {
        // write code here
        int count = 0;
        for (int i = 0; i < T.length(); i++) {
            if (T[i] == S[count]) {
                count++;
            }

            if (count == S.length()) { 
                return true;
            };
        }
        return false;
    }
};

原题扩充

基于原题扩展到leetcode的 727.最短窗口子序列

给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。

如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 ""。

如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。

示例 1：

输入：

S = "abcdebdde", T = "bde"

输出："bcde"

解释：

"bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。

"deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。

采用滑窗解法，虽然效率比不上动态规划，但是思路简单，为了避免超时，通过判断窗口左右边界是否是子串左右边界进行剪枝，可以减少不必要的窗口遍历。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return bool布尔型
     */

    static bool compare(pair<int, string> a, pair<int, string> b) {
        if (a.second.length() == b.second.length()) {
            return a.first < b.first;
        } else {
            return a.second.length()  < b.second.length();
        }
    }

    string findMinSubstring(string S, string T) {
        // write code here
        int s_len = S.size();
        int t_len = T.size();

        int start = 0;
        vector<pair<int, string>> ans;

        for (size_t left = 0; left < t_len - s_len + 1; left++)
        {
            if (T[left] != S[0]) {
                continue;
            }

            // 窗口右端点（不包含left + s_len自身） 至少从left + s_len开始， 不包含left + s_len自身
            for (size_t right = left + s_len; right <= T.length(); right++)
            {
                if (T[right - 1] != S.back()) {
                    continue;
                }

                // sub_count: 子串有效长度计数
                int sub_count = 0;
                // 以idx为起点，遍历当前窗口
                for (size_t idx = left; idx < right; idx++)
                {
                    if (T[idx] == S[sub_count]) {
                        sub_count++;
                    }

                    // 找到子串
                    if (sub_count == s_len) {
                        string substring = T.substr(left, right - left);
                        ans.push_back(std::make_pair(left, substring));
                    }
                }
            }
        }

        if (ans.size() == 0) {
            return "";
        }

        sort(ans.begin(), ans.end(), compare);
        return ans[0].second;
    }
};

找最短时用了排序算法，有点浪费性能，优化一下改成调用min算法:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return bool布尔型
     */

    static bool compare(pair<int, string> a, pair<int, string> b) {
        if (a.second.length() == b.second.length()) {
            return a.first < b.first;
        } else {
            return a.second.length()  < b.second.length();
        }
    }

    string findMinSubstring(string S, string T) {
        // write code here
        int s_len = S.size();
        int t_len = T.size();

        int start = 0;
        pair<int, string> ans = std::make_pair(T.size(), "");

        for (size_t left = 0; left < t_len - s_len + 1; left++)
        {
            if (T[left] != S[0]) {
                continue;
            }

            // 窗口右端点（不包含left + s_len自身） 至少从left + s_len开始， 不包含left + s_len自身
            for (size_t right = left + s_len; right <= T.length(); right++)
            {
                if (T[right - 1] != S.back()) {
                    continue;
                }

                // sub_count: 子串有效长度计数
                int sub_count = 0;
                // 以idx为起点，遍历当前窗口
                for (size_t idx = left; idx < right; idx++)
                {
                    if (T[idx] == S[sub_count]) {
                        sub_count++;
                    }

                    // 找到子串
                    if (sub_count == s_len) {
                        string substring = T.substr(left, right - left);
                        pair<int, string> temp_ans = std::make_pair(left, substring);
                        if (ans.second == "") {
                            ans = temp_ans;
                        } else {
                            ans = std::min(ans, temp_ans, compare);
                        }

                    }
                }
            }
        }

        return ans.second;
    }
};