串联所有单词的子串

给定一个字符串s和一些长度相同的单词words 。找出s中恰好可以由words中所有单词串联形成的子串的起始位置。
注意子串要与words中的单词完全匹配，中间不能有其他字符 ，但不需要考虑words中单词串联的顺序。

  • 示例 1：

    输入：s = “barfoothefoobarman”, words = [“foo”,”bar”]
    输出：[0,9]
    解释：
    从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
    输出的顺序不重要, [9,0] 也是有效答案。

  • 示例 2：

    输入：s = “wordgoodgoodgoodbestword”, words = [“word”,”good”,”best”,”word”]
    输出：[]

  • 示例 3：

    输入：s = “barfoofoobarthefoobarman”, words = [“bar”,”foo”,”the”]
    输出：[6,9,12]

提示：

  • 1 <= s.length <= 104
  • s 由小写英文字母组成
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] 由小写英文字母组成

Solution

解法在提交是显示示例2错误，正确答案为[8]。暂时记录下。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<int> findSubstring(std::string s, std::vector<std::string>& words) {
        std::vector<int> indexs;
        if (s.empty() || words.size() == 0 || (s.size() < words[0].size())) {
            return indexs;
        }
        int num = words.size();
        int perLen = words[0].size();
        int wordsLen = num * perLen;
        std::vector<bool> exists(num, false);
        std::string wordsStr;
        for (auto it = words.begin(); it != words.end(); ++it) {
            wordsStr += *it;
        }
        
        int index = 0;
        while (index < s.size() - wordsLen) {
            std::string wordsTmp = wordsStr;
            int i = index;
            while (!wordsTmp.empty()) {
                std::string substr = s.substr(i , perLen);
                int wordsIndex = wordsTmp.find(substr);
                if (wordsIndex == std::string::npos) {
                    break;
                }
                wordsTmp.erase(wordsIndex, perLen);
                i += perLen;
                // subStr = s.substr(i, perLen);
            }
            if (wordsTmp.empty()) {
                indexs.push_back(index);
            }
            index++;
        }
        return indexs;
    }
};

template <typename T>
void printVector(const std::vector<T> &data, int printLen = 0) {
    for (int i = 0; i < data.size(); ++i) {
        std::cout << data[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<std::string> words{"foo","bar"};
    std::string s = "barfoothefoobarman";
    printVector<int>(Solution().findSubstring(s, words));

    s = "wordgoodgoodgoodbestword";
    words = {"word","good","best","word"};
    printVector<int>(Solution().findSubstring(s, words));

    s = "barfoofoobarthefoobarman";
    words = {"bar","foo","the"};
    printVector<int>(Solution().findSubstring(s, words));
    return 0;
}