作者:
晚于: 2020-08-19 12:00:00后提交分数乘系数50%
截止日期: 2020-08-26 12:00:00
问题描述 :
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：0 9
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出时，按照索引由小到大顺序输出。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
输出：-1
s中的子串无法由words串联得到，所以输出-1
可使用以下main函数：
int main()
{
string s,str;
vector<string> words;
int n;
cin>>s;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>str;
words.push_back(str);
}
vector<int> res=Solution().findSubstring(s, words);
if (res.size()> 0)
for(int i=0; i<res.size(); i++)
{
if (i> 0)
cout<<" ";
cout<<res[i];
}
else
cout<<-1;
return 0;
}
输入说明 :
首先收入字符串s，
然后输入words中单词的数目n，
最后输入n个字符串，表示words中的单词
输出说明 :
按照索引由小到大顺序输出，或者输出-1.
输入范例 :
输出范例 :
#include <iostream> #include <vector> #include <string> #include <unordered_map> using namespace std; class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> res; if(!words.size()) return res; int single=words[0].length(); int num=words.size(); unordered_map<string,int> map1; for(const auto& t:words) map1[t]++;//设置目标map for(int start=0;start<single;start++)//设置不同的起点 { int left=start,right=start,count=0; unordered_map<string,int> map2;//当前的map while(right+single<=s.size()) { string str=s.substr(right,single);//截取一个单词 right+=single;//移动右边界 if(map1.find(str)==map1.end())//若当前单词不在target中 则重置 { count=0; map2.clear(); left=right; } else { map2[str]++; count++; //为什么是while呢 //因为左边第一个单词不一定是str while(map1[str]<map2[str])//若当前str的次数大于target中str的次数 则左移 { string temp=s.substr(left,single); map2[temp]--; left+=single; count--; } if(count==num)res.push_back(left); } } } return res; } }; int main() { string s,str; vector<string> words; int n; cin>>s; cin>>n; for(int i=0; i<n; i++) { cin>>str; words.push_back(str); } vector<int> res=Solution().findSubstring(s, words); if (res.size()> 0) for(int i=0; i<res.size(); i++) { if (i> 0) cout<<" "; cout<<res[i]; } else cout<<-1; return 0; }
原文：https://www.cnblogs.com/zmmm/p/13645775.html