# 30. Substring with Concatenation of All Words
## 1.問題
* 給一個字串, 還有一個字的list, 每個字的長度相同. 找出所有字所拼成的子字串在字串中的起始索引
## 2.想法
* 提問
* function header, parameter
* test input
* 說明想法
* 此題的目的是確認字串中是否有符合目標的子字串: 除了用字串相等外, 可以用範圍內的substr的字串是否有在map中出現, 而且次數相同, 如滿足此條件則將索引push到vector中
* 用兩個map: 第一個存放string list, 第二個map存放每次移動時, substr中字串所出現的次數
* 測試計算複雜度: O(n)
## **3.程式碼**
```
class Solution {
public:
vector findSubstring(string s, vector& words) {
vector res;
int size = words.size();
if (size== 0 || s.empty() || size* words[0].length() > s.length()) {
return res;
}
map m1;
for (int i = 0; i < size; i++) {
m1[words[i]]++;
}
for (int i = 0 ; i <= s.length() - size * words[0].length(); i++) {
map m2;
bool flag = true;
for (int j = 0; j < size; j++) {
string tmp = s.substr(i + j * words[0].length(), words[0].length());
if (m1.find(tmp) != m1.end()) {
m2[tmp]++;
} else {
flag = false;
break;
}
if (m2[tmp] > m1[tmp]) {
flag = false;
break;
}
}
if (flag) {
res.push_back(i);
}
}
return res;
}
};
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/30.-substring-with-concatenation-of-all-words.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.