串联所有单词的子串，找到所有符合条件的串联子串的起始索引

面试学习

一、题目

串联所有单词的子串

二、解题思路

2.1 定义子串长度

所有字符串 words 的长度是相同的，假设为 L。那么一个有效的串联子串的总长度应该是 L * len(words)。

2.2 滑动窗口

我们可以使用滑动窗口的方法来遍历字符串 s。窗口的大小应为 L * len(words)。在每个窗口内，我们检查是否可以找到 words 中所有字符串的一个排列。

2.3 哈希表

我们可以使用哈希表来记录 words 中每个字符串出现的次数，并使用另一个哈希表来记录当前窗口中每个字符串的出现次数。

2.4 验证子串

对于每个窗口，检查窗口中字符串的出现次数是否与 words 中字符串的出现次数一致。如果一致，则记录窗口的起始索引。

---

三、代码实现

// Helper function to check if two hash tables are equal
int areHashTablesEqual(int *hash1, int *hash2, int size) {for (int i = 0; i < size; i++) {if (hash1[i] != hash2[i]) {return 0;}}return 1;
}void findSubstring(char *s, char **words, int wordsSize, int wordLen, int *result, int *returnSize) {int sLen = strlen(s);int concatLen = wordsSize * wordLen;int *wordCount = (int *)calloc(256, sizeof(int));int *windowCount = (int *)calloc(256, sizeof(int));// Initialize wordCount hash tablefor (int i = 0; i < wordsSize; i++) {for (int j = 0; j < wordLen; j++) {wordCount[(unsigned char)words[i][j]]++;}}for (int i = 0; i <= sLen - concatLen; i++) {memset(windowCount, 0, 256 * sizeof(int));int j;for (j = 0; j < wordsSize; j++) {char *word = s + i + j * wordLen;for (int k = 0; k < wordLen; k++) {windowCount[(unsigned char)word[k]]++;}}if (areHashTablesEqual(wordCount, windowCount, 256)) {result[(*returnSize)++] = i;}}free(wordCount);free(windowCount);
}int* findSubstringIndices(char *s, char **words, int wordsSize, int *returnSize) {int wordLen = strlen(words[0]);int *result = (int *)malloc(sizeof(int) * 1000); // Allocate enough space for result*returnSize = 0;findSubstring(s, words, wordsSize, wordLen, result, returnSize);return result;
}

---

四、代码讲解

4.1 areHashTablesEqual

检查两个哈希表是否相等。

4.2 findSubstring

主要逻辑，包括：

• 初始化哈希表 wordCount 记录 words 中所有字符串的出现次数。
• 使用滑动窗口方法检查每个窗口内的字符出现次数是否匹配 wordCount。
• 如果匹配，将窗口的起始索引存入结果数组。

4.3 findSubstringIndices

封装 findSubstring 函数，返回结果数组。

五、测试代码

串联所有单词的子串，找到所有符合条件的串联子串的起始索引