地址：https://leetcode.com/problems/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 “barfoor” 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: []

理解：

就是寻找子串的起始位置，使得该位置开始的子串包含且仅包含一次words中的所有字符串。为了内层多次遍历，采用滑动窗口的思想，这样，外层只需要从0到words[0].length()-1就可以了，因为words[0].length()开始的在0开始的遍历中已经判断过了。

实现：

class Solution {

public:

vector findSubstring(string s,vector& words) {

vector res;

if (words.empty() || s.empty()) return res;

unordered_map table;

for (string word : words)

table[word]++;

int n = s.length(),num = words.size(),len = words[0].length();

int size = num*len;

if (s.length() < size) return res;

int beg = 0,end = 0,counter = table.size();

//there are only len windows to judge

unordered_map curr(table);

for (int i = 0; i < len; i++) {

beg = i;

end = i;

curr = table;

counter = table.size();

while (end + len - 1 < s.length()) {

string last = s.substr(end,len);

if (curr.count(last)) {

curr[last]--;

if(curr[last]==0) counter--;

}

if (end + len - beg == size) {

if (counter == 0)

res.push_back(beg);

string first = s.substr(beg,len);

if (curr.count(first)) {

curr[first]++;

if (curr[first] > 0)

counter++;

}

beg += len;

}

end += len;

}

}

return res;

}

};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!