【每日一题】30. Substring with Concatenation of All Words
【每日一题】30. Substring with Concatenation of All Words
题目描述
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
Example 1:
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.Example 2:
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
题解
想法是先将words中单词的所有排列组合串联形成的字符串存储起来，然后再将这些子串和字符串s进行依次比较，但是这种方法时间复杂度过高。
再一次分析，我们发现如果字符串s中出现了words中所有单词的串联字符串，words数组中的单词出现的顺序并不重要，可以将words的所有单词整合到一个hash表里，同时记录单词出现的次数；然后遍历s的和words拼接串长度相等的子串t，在这个字串中，依次找到每个单词长度相同的小串，判断是否出现在hash表中，同时创建另一个hash表用于存储这个子串t中words各个单词出现的次数：
- 如果t的长度相等的某个单词没有出现在第一个hash表中，直接退出
- 如果t的长度相等的某个单词出现的次数比第一个hash中的次数要多，也退出；
- 这个子串t遍历完成，将这个t的起始位置记录下来。
完整代码：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
if (s.empty() || words.empty())
return res;
int size = words.size(), len = words[0].size();
unordered_map<string, int> table;
for (auto &word : words)
table[word]++;
// 遍历s子串::unsigned int->int类型转换
for (int i=0; i<= int(s.size()-size*len); ++i){
int j = 0;
unordered_map<string, int> tmp;
for (; j< size; j++){
string sub = s.substr(i+j*len, len);
if (!table.count(sub))
break;
tmp[sub]++;
if (tmp[sub] > table[sub])
break;
}
if (j == size)
res.push_back(i);
}
return res;
}
};值得注意的是for循环中用到了强制类型转换，cpp中string.size()返回类型是unsign ed int，无符号数，无符号数与有符号数运算时，有符号数被转换成无符号数进行运算，当s.size() < size * len时，s.size() - size*len结果为负数，unsigned转换后变为一个极大值UMAX-abs(s.size()-size*len),导致越界出错，所以这里做了一个int类型转换，保证当s串长度小于words数组拼接长度时，不循环。
关于unsigned更详细的可以看https://blog.csdn.net/ljianhui/article/details/10367703