[已解决]力扣的题76. 最小覆盖子串

202021130162 · 发表于 2021-8-10 20:23:25

新写的一个想法,在评论区找不到参考,可以通过题目给的测试,但提交时的测试用例:"a""a";返回结果是"",不知道哪里错了
题目链接:https://leetcode-cn.com/problems/minimum-window-substring/

class Solution {
public:
    string minWindow(string s, string t) {
        int k=0;
        int p=0,q=0;
        int Minresult=s.size();
        int Min=0;
        string result,r;
        for(int i=0;i<s.size()-t.size();i++)
        {
            for(int j=i;j<s.size()&&k<t.size();j++)
            {
                if(t[k]==s[j])
                {
                    k++;
                    Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
                    j=i-1;
                    continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
            {
                Minresult=Min-i+1;
                p=Min;
                q=i;                            //用p,q存储最小子串的首尾位置
            }
            Min=0;
            k=0;
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p==0&&q==0)
        {
            result[0]='""';
        }
        else
        {
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
        }
        return result;
    }
};

希望大佬们可以看看哪里错了,谢谢!

最佳答案

月排行榜 / 总排行榜

人造人

2021-8-10 20:23:26

这个算法不对，你现在是 j 一直后移，k 是在匹配到字符才后移，题目要求不是这样的
用这个思路写吧，虽然这个思路超时，但是至少正确

这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。

for(size_t j = i; j < s.size() && k < t.size(); j++)
{
    if(t[k] == s[j])
    {
        k++;

        // max 赋值给 min ?
        // 把最大的赋值给最小的？这是什么操作？
        Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
        Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
        j = i - 1;

        // 为什么要加这个 continue ?
        // 这里的 continue 对程序没有任何影响
        // 加不加都一样
        //continue;
    }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
}

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    //void Delete(string x,int n)
    void Delete(string &x,int n)
    {
        size_t i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

    string minWindow(string s, string t) {
        size_t k = 0;
        int p = -1, q = -1;
        size_t Minresult = s.size();
        size_t Min = -1;
        string result, r, S = s;
#if 0
        if(s.size()<t.size())
        {
            /*
            result="";
            return result;
            */
            return "";
        }
        if(s == t)
        {
            return s;
        }
#endif
        if(s == t) return s;
        if(s.size() < t.size()) return "";
        for(size_t i = 0; i <= s.size() - t.size(); i++)
        {

            std::cout << "i: " << i << std::endl;

            for(size_t j = i; j < s.size() && k < t.size(); j++)
            {

                std::cout << "k: " << k << ", " << "t[k]: " << "'" << t[k] << "'" << std::endl;
                std::cout << "j: " << j << ", " << "s[j]: " << "'" << s[j] << "'" << std::endl;
                std::cout << std::endl;

                if(t[k] == s[j])
                {
                    k++;

                    // max 赋值给 min ?
                    // 把最大的赋值给最小的？这是什么操作？
                    Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
                    Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
                    j = i - 1;

                    // 为什么要加这个 continue ?
                    // 这里的 continue 对程序没有任何影响
                    // 加不加都一样
                    //continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult > Min - i && (Min - i + 1) >= t.size() && k == t.size())
            {
                Minresult = Min - i + 1;
                p = Min;
                q = i;                            //用p,q存储最小子串的首尾位置
            }
            Min = -1;
            k = 0;
            s = S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p == -1 && q == -1) return "";
        return string(&s[q], &s[p + 1]);
#if 0
        if(p==-1&&q==-1)
        {
            result="";
        }
        else
        {
            /*
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
            */
            result = string(&s[q], &s[p + 1]);
        }
        return result;
#endif
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

跳转到最佳答案楼层

人造人 · 发表于 2021-8-10 20:23:26

这个算法不对，你现在是 j 一直后移，k 是在匹配到字符才后移，题目要求不是这样的
用这个思路写吧，虽然这个思路超时，但是至少正确

这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。

for(size_t j = i; j < s.size() && k < t.size(); j++)
{
    if(t[k] == s[j])
    {
        k++;

        // max 赋值给 min ?
        // 把最大的赋值给最小的？这是什么操作？
        Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
        Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
        j = i - 1;

        // 为什么要加这个 continue ?
        // 这里的 continue 对程序没有任何影响
        // 加不加都一样
        //continue;
    }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
}

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    //void Delete(string x,int n)
    void Delete(string &x,int n)
    {
        size_t i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

    string minWindow(string s, string t) {
        size_t k = 0;
        int p = -1, q = -1;
        size_t Minresult = s.size();
        size_t Min = -1;
        string result, r, S = s;
#if 0
        if(s.size()<t.size())
        {
            /*
            result="";
            return result;
            */
            return "";
        }
        if(s == t)
        {
            return s;
        }
#endif
        if(s == t) return s;
        if(s.size() < t.size()) return "";
        for(size_t i = 0; i <= s.size() - t.size(); i++)
        {

            std::cout << "i: " << i << std::endl;

            for(size_t j = i; j < s.size() && k < t.size(); j++)
            {

                std::cout << "k: " << k << ", " << "t[k]: " << "'" << t[k] << "'" << std::endl;
                std::cout << "j: " << j << ", " << "s[j]: " << "'" << s[j] << "'" << std::endl;
                std::cout << std::endl;

                if(t[k] == s[j])
                {
                    k++;

                    // max 赋值给 min ?
                    // 把最大的赋值给最小的？这是什么操作？
                    Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
                    Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
                    j = i - 1;

                    // 为什么要加这个 continue ?
                    // 这里的 continue 对程序没有任何影响
                    // 加不加都一样
                    //continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult > Min - i && (Min - i + 1) >= t.size() && k == t.size())
            {
                Minresult = Min - i + 1;
                p = Min;
                q = i;                            //用p,q存储最小子串的首尾位置
            }
            Min = -1;
            k = 0;
            s = S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p == -1 && q == -1) return "";
        return string(&s[q], &s[p + 1]);
#if 0
        if(p==-1&&q==-1)
        {
            result="";
        }
        else
        {
            /*
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
            */
            result = string(&s[q], &s[p + 1]);
        }
        return result;
#endif
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

人造人 · 发表于 2021-8-11 00:04:00

for(int i=0;i<s.size()-t.size();i++)
s.size() 是 1
t.size() 是 1
1 - 1 = 0
for(int i=0;i<0;i++)
提问：这个循环执行几次？

202021130162 · 发表于 2021-8-11 17:35:49

人造人发表于 2021-8-11 00:04
for(int i=0;i

!哦哦哦知道了!

202021130162 · 发表于 2021-8-11 18:07:37

本帖最后由 202021130162 于 2021-8-11 18:08 编辑

人造人发表于 2021-8-11 00:04
for(int i=0;i

我改了一下之后又有新的问题了,如果子串里面有重复的字符,就会出错
例如:
输入:
"acbbaca"
"aba"
输出:
"bba"
预期结果:
"baca"

代码如下:

class Solution {
public:
    void Delete(string x,int n)
    {
        int i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' '; 
    }
    
    string minWindow(string s, string t) {
        int k=0;
        int p=-1,q=-1;
        int Minresult=s.size();
        int Min=-1;
        string result,r,S=s;
        if(s.size()<t.size())
        {
            result[0]='""';
            return result;
        }
        if(s==t)
        {
            return s;
        }
        for(int i=0;i<=s.size()-t.size();i++)
        {
            for(int j=i;j<s.size()&&k<t.size();j++)
            {
                if(t[k]==s[j])
                {
                    k++;
                    Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
                    Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素    
                    j=i-1;
                    continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
            {
                Minresult=Min-i+1;
                p=Min;
                q=i;                            //用p,q存储最小子串的首尾位置
            }
            Min=-1;
            k=0;
            s=S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p==-1&&q==-1)
        {
            result[0]='""';
        }
        else
        {
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
        }
        return result;
    }
};

人造人 · 发表于 2021-8-11 18:43:09

202021130162 发表于 2021-8-11 18:07
我改了一下之后又有新的问题了,如果子串里面有重复的字符,就会出错
例如:
输入:

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    void Delete(string x,int n)
    {
        int i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' '; 
    }
    
    string minWindow(string s, string t) {
        int k=0;
        int p=-1,q=-1;
        int Minresult=s.size();
        int Min=-1;
        string result,r,S=s;
        if(s.size()<t.size())
        {
            result[0]='""';
            return result;
        }
        if(s==t)
        {
            return s;
        }
        for(int i=0;i<=s.size()-t.size();i++)
        {
            for(int j=i;j<s.size()&&k<t.size();j++)
            {
                if(t[k]==s[j])
                {
                    k++;
                    Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
                    Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素    
                    j=i-1;
                    continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
            {
                Minresult=Min-i+1;
                p=Min;
                q=i;                            //用p,q存储最小子串的首尾位置
            }
            Min=-1;
            k=0;
            s=S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p==-1&&q==-1)
        {
            result[0]='""';
        }
        else
        {
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
        }
        return result;
    }
};

int main() {
    std::cout << Solution().minWindow("acbbaca", "aba") << std::endl;
    return 0;
}

$ g++ -g -Wall -o main main.cpp
main.cpp:26:23: warning: multi-character character constant [-Wmultichar]
   26 |             result[0]='""';
      |                       ^~~~
main.cpp:59:23: warning: multi-character character constant [-Wmultichar]
   59 |             result[0]='""';
      |                       ^~~~
main.cpp: In member function ‘void Solution::Delete(std::string, int)’:
main.cpp:11:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   11 |         for(i=n;i<x.size()-1;i++)
      |                 ~^~~~~~~~~~~
main.cpp: In member function ‘std::string Solution::minWindow(std::string, std::string)’:
main.cpp:26:23: warning: overflow in conversion from ‘int’ to ‘std::basic_string<char>::value_type’ {aka ‘char’} changes value from ‘8738’ to ‘34’ [-Woverflow]
   26 |             result[0]='""';
      |                       ^~~~
main.cpp:33:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   33 |         for(int i=0;i<=s.size()-t.size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~
main.cpp:35:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   35 |             for(int j=i;j<s.size()&&k<t.size();j++)
      |                         ~^~~~~~~~~
main.cpp:35:38: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   35 |             for(int j=i;j<s.size()&&k<t.size();j++)
      |                                     ~^~~~~~~~~
main.cpp:46:42: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   46 |             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
      |                                 ~~~~~~~~~^~~~~~~~~~
main.cpp:46:55: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   46 |             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
      |                                                      ~^~~~~~~~~~
main.cpp:59:23: warning: overflow in conversion from ‘int’ to ‘std::basic_string<char>::value_type’ {aka ‘char’} changes value from ‘8738’ to ‘34’ [-Woverflow]
   59 |             result[0]='""';
      |                       ^~~~

语法错误
result[0]='""'; // 这是什么操作？

202021130162 · 发表于 2021-8-11 20:24:32

人造人发表于 2021-8-11 18:43
语法错误
result[0]='""'; // 这是什么操作？

这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

而且我在leedcode上没报错啊

登录/注册后可看大图

人造人 · 发表于 2021-8-11 22:57:47

202021130162 发表于 2021-8-11 20:24
这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不 ...

你 C++ 语法不过关呀，给一个字符位置赋值一个字符串？
result[0]='""';

下面这 3 个可以
result[0] = '0';
result[0] = '\0';
result[0] = 123;

还有，有符号数和无符号数不要混用
这样就没有语法错误了，但是还有逻辑错误，这个代码无法通过测试的，我看不懂你的算法，可以说一说你的算法实现思路吗？

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    void Delete(string x,int n)
    {
        //int i;
        size_t i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

    string minWindow(string s, string t) {
        //int k=0;
        size_t k=0;
        int p=-1,q=-1;
        //int Minresult=s.size();
        size_t Minresult=s.size();
        //int Min=-1;
        size_t Min=-1;
        string result,r,S=s;
        if(s.size()<t.size())
        {
            //result[0]='""';
            result="";
            return result;
        }
        if(s==t)
        {
            return s;
        }
        //for(int i=0;i<=s.size()-t.size();i++)
        for(size_t i=0;i<=s.size()-t.size();i++)
        {
            //for(int j=i;j<s.size()&&k<t.size();j++)
            for(size_t j=i;j<s.size()&&k<t.size();j++)
            {
                if(t[k]==s[j])
                {
                    k++;
                    Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
                    Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
                    j=i-1;
                    continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
            {
                Minresult=Min-i+1;
                p=Min;
                q=i;                            //用p,q存储最小子串的首尾位置
            }
            Min=-1;
            k=0;
            s=S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p==-1&&q==-1)
        {
            //result[0]='""';
            result="";
        }
        else
        {
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
        }
        return result;
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

我自己也写了一个，但是算法选错了，超时
要学着调试程序呀，其实就是不断调试程序，把不通过的测试一个一个的解决
我的算法思路
这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。
参考: https://www.nowcoder.com/questio ... c7c9d322d12ca7955ac

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        size_t begin = 0, end;
        string s_bak = s;
        string result;
        while(true) {
            if(s.size() - begin < t.size()) break;
            while(begin < s.size() && t.find(s[begin]) == string::npos) ++begin;
            end = begin; if(begin >= s.size()) break;
            for(size_t i = 0; i < t.size(); ++i) {
                size_t pos = s.find(t[i], begin);
                if(pos == string::npos) {
                    end = begin; break;
                } else {
                    s[pos] = -1;
                    if(pos >= end) end = pos + 1;
                }
            }
            s = s_bak;
            string new_result(&s[begin], &s[end]);
            if(!new_result.empty()) {
                if(result.empty() || result.size() > new_result.size())
                    result = new_result;
            }
            ++begin;
        }
        return result;
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

试了 19 次，最后 3 次超时，我目前对这个算法没招了，我想不到如何修改这个算法了，要通过这个测试，估计得换一个算法了，这个算法对这样的输入没办法

人造人 · 发表于 2021-8-11 22:59:30

202021130162 发表于 2021-8-11 20:24
这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不 ...

leedcode 当然不报错了，它又不是用最高级别的警告编译代码的

人造人 · 发表于 2021-8-11 23:40:37

这个函数没有如何效果
有没有调用这个函数都不会对程序有任何影响

    void Delete(string x,int n)
    {
        int i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

要传引用

    void Delete(string &x, int n)
    {
        int i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

202021130162 · 发表于 2021-8-12 16:03:11

人造人发表于 2021-8-11 22:57
你 C++ 语法不过关呀，给一个字符位置赋值一个字符串？
result[0]='""';

我的思路:
1.对s中的每个字符s[0],s[1]...,都去查找以它开头的子串,子串中包含t中所有的字符
2.得到了许多组字符串,再从这些字符中找到长度最小的字符串,即为答案

然后对于那个Delete函数,想要实现的功能就是:
由于题目字符串t中会有重复字符,那么在查找s的子串时,我碰到一个t中的字符,就把对应的s字符删掉,这样就可以让s的子串中包含对应数量的t字符
避免出现以下情况:
输入:s=abca,t=aba
输出:ab

人造人 · 发表于 2021-8-12 17:31:36

看不懂你的代码
这个代码，输入 Solution().minWindow("bbaa", "aba")
执行到 69 行的时候 p 和 q 都是 -1，也就是 58 行的 if 每一次都不成立
60，61，62 行的代码没有执行过

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    //void Delete(string x,int n)
    void Delete(string &x,int n)
    {
        size_t i;
        for(i=n;i<x.size()-1;i++)
        {
            x[i]=x[i+1];
        }
        x[i-1]=' ';
    }

    string minWindow(string s, string t) {
        size_t k=0;
        int p=-1,q=-1;
        size_t Minresult=s.size();
        size_t Min=-1;
        string result,r,S=s;
        if(s.size()<t.size())
        {
            /*
            result="";
            return result;
            */
            return "";
        }
        if(s==t)
        {
            return s;
        }
        for(size_t i=0;i<=s.size()-t.size();i++)
        {
            for(size_t j=i;j<s.size()&&k<t.size();j++)
            {
                if(t[k]==s[j])
                {
                    k++;

                    // max 赋值给 min ?
                    // 把最大的赋值给最小的？这是什么操作？
                    Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
                    Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
                    j=i-1;

                    // 为什么要加这个 continue ?
                    // 这里的 continue 对程序没有任何影响
                    // 加不加都一样
                    //continue;
                }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
            }
            if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
            {
                Minresult=Min-i+1;
                p=Min;
                q=i;                            //用p,q存储最小子串的首尾位置
            }
            Min=-1;
            k=0;
            s=S;                                //还原s,开始下一次循环
        }
        //循环结束,返回以q开头,p结束的最小子串
        if(p==-1&&q==-1)
        {
            result="";
        }
        else
        {
            /*
            for(int h=q;h<=p;h++)
            {
                result.push_back(s[h]);
            }
            */
            result = string(&s[q], &s[p + 1]);
        }
        return result;
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

人造人 · 发表于 2021-8-12 18:02:37

参考这个

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
    string minWindow(string s, string t) {
        size_t begin = 0, end;
        string s_bak = s;
        string result;
        while(true) {
            if(s.size() - begin < t.size()) break;
            while(begin < s.size() && t.find(s[begin]) == string::npos) ++begin;
            end = begin; if(begin >= s.size()) break;
            for(size_t i = 0; i < t.size(); ++i) {
                size_t pos = s.find(t[i], begin);
                if(pos == string::npos) {
                    end = begin; break;
                } else {
                    s[pos] = -1;
                    if(pos >= end) end = pos + 1;
                }
            }
            s = s_bak;
            string new_result(&s[begin], &s[end]);
            if(!new_result.empty()) {
                if(result.empty() || result.size() > new_result.size())
                    result = new_result;
            }
            ++begin;
        }
        return result;
    }
};

int main() {
    std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    return 0;
}

202021130162 · 发表于 2021-8-14 19:15:17

人造人发表于 2021-8-12 18:02
参考这个

好的,还是得用滑动窗口写,谢谢啦!

账号		自动登录	找回密码
密码			立即注册