题目描述
给定一个字符串 s
和一个字符串数组 words
。 words
中所有字符串 长度相同。
s
中的 串联子串 是指一个包含 words
中所有字符串以任意顺序排列连接起来的子串。
- 例如,如果
words = ["ab","cd","ef"]
, 那么"abcdef"
,"abefcd"
,"cdabef"
,"cdefab"
,"efabcd"
, 和"efcdab"
都是串联子串。"acdbef"
不是串联子串,因为他不是任何words
排列的连接。
返回所有串联子串在 s
中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出:[6,9,12] 解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
和s
由小写英文字母组成
请问您在哪类招聘中遇到此题?
1/5
社招
校招
实习
未遇到
通过次数
196.5K
提交次数
502.9K
通过率
39.1%
思路一,暴力遍历,通过178/179
字典(字符串数组)里每个单词的长度是固定的,假设字典里有word_num个单词,每个单词的长度为word_size。那么我们的任务就是在s中找到所有长度为word_num*word_size的子串,判断这个子串能不能由字典里的单词串联起来(其中串联指的是words里面的任意一个排列的连接)。
这个方法的代码比较好写,先用一个哈希表存放字典中每个单词出现的次数。每次判断子串时再创键一个新表,遍历word_num个单词,若某个单词在旧表中没有出现过或者是新表出现次数比旧表的多,就说明这个子串不符合条件。
实现代码:
class Solution {
public:
unordered_map<string,int> mp;
bool judge(string& s,int wordNumber,int wordLength,int begin)//单词个数,单词的字母个数
{
unordered_map<string,int> newMp;
for(int i=begin;i<begin+wordNumber*wordLength;i+=wordLength)
{
string temp=s.substr(i,wordLength);
if(mp.find(temp)==mp.end()) return false;//字符串数组中没出现
newMp[temp]++;
if(newMp[temp]>mp[temp]) return false;//多出现了
}
return true;
}
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
for(int i=0;i<words.size();i++)
{
mp[words[i]]++;
}
int n=words.size(),m=words[0].size(),ls=s.length();
int left=0,right=n*m;
for(int i=0;i<=ls-n*m;i++)
{
bool flag=judge(s,n,m,i);
if(flag) ans.push_back(i);
}
return ans;
}
};
思路二:哈希表+滑动窗口+类KMP思想,全部通过
我们学过kmp算法的都知道,在字符串匹配时(假设是在s串里寻找s1串),如果比较懂s为下标i,s1为下标j的位置时发现两个串暂时不相等,用BF算法的思想来说i要返回到i-j+1的位置,j要回到0的位置(这里假设下标从0开始),然后重新匹配。
但是按照kmp算法的思想来说,既然s1已经比到了下标 j 的位置,那么说明s1的前 j 个字符和s[i]的前j个字符是相等的,而如果s1的最前面 k 个字符和s[i]的前 k 个字符相等的话,i就不用回溯,而 j 只需要回溯到第 k+1 个位置就行。
总而言之,kmp算法最核心的思想就是保留了之前搜索时的信息,方便下一次搜索。
代码:
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
int word_nums = words.size();
int word_size = words[0].size();
int ls = s.length();
unordered_map<string, int> mp1;
for (int i = 0; i < word_nums; i++)
mp1[words[i]]++;
for (int i = 0; i < word_size; i++)
{
int k;
unordered_map<string, int> mp2;
bool flag = false;//表示同一个i下,上次匹配成功
for (int j = i; j + word_nums * word_size <= ls; j += word_size)
{//从下标j开始的子串
if (!flag) k = j;
for (; k < j + word_nums * word_size; k += word_size)
{
string temp = s.substr(k, word_size);
if (mp1.find(temp) == mp1.end()) {
//下标k之前(包括下标k)开始的子串都不用判断了
j = k;//j=k+word_size;外层的循环j还会加一次word_size
//之前存储的结果也作废了
flag = false;
mp2.clear();
break;
}
else {
mp2[temp]++;
//重复次数过多时,从下表j开始就不行了
//重复出现的子串是temp,所以只要从j开始寻找第一次出现temp的位置index,然后从index+word_size开始匹配
if (mp2[temp] > mp1[temp]) {
int index = j;
string t = s.substr(index, word_size);
while (t != temp) {
index += word_size;
mp2[t]--;
t = s.substr(index, word_size);
}
j = index + word_size;//index+=word_size;外层循环会加一次word_size
mp2[temp]--;
}
}
}
//从j开始的子串完全匹配
if (k == j + word_nums * word_size)
{
ans.push_back(j);
//移除从j开始的子串的第一个单词
string t = s.substr(j, word_size);
mp2[t]--;
if (mp2[t] == 0) mp2.erase(t);
//k += word_size;//只有一个单词没有匹配好,所以从k就从k+word_size开始
flag = true;
}
}
}
return ans;
}
};