题目描述

小美和小团在玩一个游戏，小美任意给出一个大字符串str1以及一个独立的小字符串str2，小团需要从这个大字符串str1里找到包含独立小字符串str2中所有字符的最小子字符串str3；
例如，小美给出一个大字符串"meituan2019"和一个子字符串"i2t"，那么小团给出的答案就应该是"ituan2"；

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

分析：
字符串查找题，在字符串1中查找字符串2的内容是否存在。
先对特殊数据进行处理，然后开始遍历str1查找str2的内容，若查找到就将下标进行标记，最终得到了str1中包含str2所有字符串的最小子字符串的最大下标max和最小下标min，在str1中截取str1.substr[min，max-min+1]即可。

伪代码：

//C++
定义字符串str1和str2指针；
定义下标max与min；
输入这两个字符串；//特殊处理
str2为空时，返回整个str1；
str1中没有完整包含str2的所有字符串，返回空字符串"";//处理
len1 = str1.size();
len2 = str2.size();
遍历str1：
{if(str1[i] == str[j]){if(i>max)max = i;if(i<min)min = i;index++;//下标统计}
}
if(index < len2)	return "";
else if(index == 0)return str1;
else if(index == len2)return str1.substr(min, max-min+1);释放动态分配内存；
return 0；

代码：

#include<iostream>
#include<string>
using namespace std;string find(string str1, string str2)
{//特殊处理if(str2 == ""){	return str1;//str2为空时，返回整个str1；}//处理int len1 = str1.size();int len2 = str2.size();int max=0, min=len1, index=0;for(int i=0;i<len1;i++){for(int j=0;j<len2;j++){if(str1[i] == str2[j]){if(i>max)max = i;if(i<min)min = i;index++;//下标统计}}}if(index < len2)	{return "";//str1中没有完整包含str2的所有字符串，返回空字符串"";}else if(index == len2){return str1.substr(min, max-min+1);}return 0;
}int main()
{//char *str1, *str2;string str1 = "meituan2019";string str2 = "it2";string str3 = find(str1, str2); cout<<str3<<endl;return 0;}

笔记：

• 以后把方法都写成一个函数，在主函数里调用，主函主要是用来测试方法定义的是否有误，作为测试的工具。