寻找最小子字符串：要从大字符串str1里找到包含独立小字符串str2中所有字符的最小子字符串str3；

Question

1、str1中有可能没有完整包含str2所有字符的情况，此时返回""，即为空字符串；
2、str1不会为空，但str2有可能为空，此时返回整个str1；
3、str2可能存在重复的字符，此时str3需要包含相等数量该字符；
示例
输入
te123sttest123
test
输出
test

string getMinString(string str1, string str2) {
    // write code here
    if (str2 == "") {
        return str1;
    }
    string ans;
    int start = 0, index = 0, end = str1.length();
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 0; j < str2.length(); j++) {
            if (str1[i] == str2[j]) {
                if (i > start)
                    start = i;
                if (i < end)
                    end = i;
                index++;
                break;
            }
                
        }        
    }
    if (index < str2.length())
        return "";
    return str1.substr(end, start - end + 1);
}

Answer 1

你这个题目其实就是判断str1是否包含str2啊，如果包含，就输出str2(str3包含str2的所有字符，也就是str2)。
比如str1="tehaha"，str2="test"，输出的是""，而不是te这个最短匹配。
代码修改如下：

#include <iostream>
#include <string>
using namespace std;

string getMinString(string str1, string str2) {
    // write code here
    if (str2.empty()) { //修改1
        return str1;
    }
    string ans;
    //int maxlen = 0; //最大匹配字符长度
    
    for (int i = 0; i < str1.length(); i++) {
        int j = 0;
        for ( j = 0; j < str2.length(); j++) {
            //修改
            if (str1[i + j] == str2[j]) 
                continue;
            else {
                break;
            }
        } 
        //如果找到str2的所有字符，直接返回str2就可以了
        if (j == str2.length())
            return str2;
        /*if (j > maxlen) {
                    maxlen = j;
                    ans = str1.substr(i, maxlen);
                }*/
    }
    return "";
    /*if (maxlen == 0)
        return "";
    else
        return ans;*/
}

int main()
{
    string s1 = "te123sttest123";
    string s2 = "test";
    cout << getMinString(s1,s2);
    return 0;
}

如果你要输出最短匹配，也就是：string s1 = "te123st123"; string s2 = "test";输出te，代码如下：

#include <iostream>
#include <string>
using namespace std;

string getMinString(string str1, string str2) {
    // write code here
    if (str2.empty()) { //修改1
        return str1;
    }
    string ans;
    int maxlen = 0; //最大匹配字符长度

    for (int i = 0; i < str1.length(); i++) {
        int j = 0;
        for (j = 0; j < str2.length(); j++) {
            //修改
            if (str1[i + j] == str2[j])
                continue;
            else {
                break;
            }
        }
        //如果找到str2的所有字符，直接返回str2就可以了
        if (j == str2.length())
            return str2;
        if (j > maxlen) {
            maxlen = j;
            ans = str1.substr(i, maxlen);
        }
    }
    
    if (maxlen == 0)
        return "";
    else
        return ans;
}

int main()
{
    string s1 = "te123st123";
    string s2 = "test";
    cout << getMinString(s1, s2);
    return 0;
}