力扣第三十题——串联所有单词的子串

内容介绍

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示：

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

完整代码

 typedef struct {char key[32];int val;UT_hash_handle hh;
} HashItem;int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){    int m = wordsSize, n = strlen(words[0]), ls = strlen(s);int *res = (int *)malloc(sizeof(int) * ls);int pos = 0;for (int i = 0; i < n; i++) {if (i + m * n > ls) {break;}HashItem *diff = NULL;char word[32] = {0};for (int j = 0; j < m; j++) {snprintf(word, n + 1, "%s", s + i + j * n);HashItem * pEntry = NULL;HASH_FIND_STR(diff, word, pEntry);if (NULL == pEntry) {pEntry = (HashItem *)malloc(sizeof(HashItem));strcpy(pEntry->key, word);pEntry->val = 0;HASH_ADD_STR(diff, key, pEntry);} pEntry->val++;            }for (int j = 0; j < m; j++) {HashItem * pEntry = NULL;HASH_FIND_STR(diff, words[j], pEntry);if (NULL == pEntry) {pEntry = (HashItem *)malloc(sizeof(HashItem));strcpy(pEntry->key, words[j]);pEntry->val = 0;HASH_ADD_STR(diff, key, pEntry);} pEntry->val--;if (pEntry->val == 0) {HASH_DEL(diff, pEntry);free(pEntry);}}for (int start = i; start < ls - m * n + 1; start += n) {if (start != i) {char word[32];snprintf(word, n + 1, "%s", s + start + (m - 1) * n);HashItem * pEntry = NULL;HASH_FIND_STR(diff, word, pEntry);if (NULL == pEntry) {pEntry = (HashItem *)malloc(sizeof(HashItem));strcpy(pEntry->key, word);pEntry->val = 0;HASH_ADD_STR(diff, key, pEntry);} pEntry->val++;if (pEntry->val == 0) {HASH_DEL(diff, pEntry);free(pEntry);}snprintf(word, n + 1, "%s", s + start - n);pEntry = NULL;HASH_FIND_STR(diff, word, pEntry);if (NULL == pEntry) {pEntry = (HashItem *)malloc(sizeof(HashItem));strcpy(pEntry->key, word);pEntry->val = 0;HASH_ADD_STR(diff, key, pEntry);} pEntry->val--;if (pEntry->val == 0) {HASH_DEL(diff, pEntry);free(pEntry);}}if (HASH_COUNT(diff) == 0) {res[pos++] = start;}}HashItem *curr, *tmp;HASH_ITER(hh, diff, curr, tmp) {HASH_DEL(diff, curr);  free(curr);      }}*returnSize = pos;return res;
}

思路详解

整体思路

初始化：确定单词长度n，单词数量m，字符串s的长度ls，并分配一个数组res用于存储结果。
遍历所有可能的起始位置：由于每个单词的长度是n，所以可能的起始位置最多有n个。
构建哈希表：对于每个起始位置，构建一个哈希表来存储words数组中每个单词出现的次数。
检查子串：从当前起始位置开始，每次移动一个单词长度n，检查当前子串是否由words中的单词组成。
更新哈希表：每次移动子串时，更新哈希表中的计数，如果计数为0，则从哈希表中删除。
记录结果：如果哈希表为空，说明找到了一个符合条件的子串，记录其起始索引。
清理哈希表：在每次循环结束后，清理哈希表，释放内存。

详细步骤

初始化变量：m是words数组的长度，n是每个单词的长度，ls是字符串s的长度。res数组用于存储结果，pos用于记录结果数组的当前索引。
外层循环：遍历所有可能的起始位置i，最多有n个。如果起始位置加上m * n超过s的长度，则结束循环。
构建哈希表：对于每个起始位置，创建一个哈希表diff，并初始化它，将words数组中的每个单词加入哈希表，并设置其值为1。
内层循环：从当前起始位置开始，每次向前移动一个单词长度n，进行以下操作：
- 如果不是起始位置，则更新哈希表，移除当前子串的第一个单词，并添加新的单词。
- 检查哈希表是否为空，如果为空，则说明找到了一个符合条件的子串，记录其起始索引。
清理哈希表：在每次外层循环结束后，遍历哈希表，删除所有条目，并释放内存。
返回结果：将结果数组的长度赋值给returnSize，并返回结果数组res。