【每日一题】30. Substring with Concatenation of All Words_给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 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.
1
2
3
4
5
6

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []
1
2
3
4

给定一个字符串 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

值得注意的是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

---