30. 串联所有单词的子串
C代码：滑动窗口、字符串异位段文章来源：https://www.toymoban.com/news/detail-433452.html
// 此题是 字母异位词 的进阶题；字符串异位段
// 1、创建words的哈希表，记录word、次数、下标idx（对比438，相当于是判断哈希数组相等！）
// 2、类比判断哈希数组相等的条件：遍历每一个str，str出现在words中，次数相等，窗口的长度与words所有串的长度相等！
// 3、str不出现在words中，l右移一个step，清空hash，重新开始；
// 4、hash[idx] > cnt 滑动窗口左移；
typedef struct {
char *str;
int cnt;
int idx;
UT_hash_handle hh;
} HashTable;
HashTable* AddHash(char **words, int wordsSize) {
HashTable* head = NULL;
HashTable* out = NULL;
for (int r = 0; r < wordsSize; r++) {
HASH_FIND_STR(head, words[r], out);
if(NULL == out) {
out = (HashTable*)malloc(sizeof(HashTable));
out->str = words[r];
out->cnt = 1;
out->idx = r;
HASH_ADD_STR(head, str, out);
} else {
out->cnt++;
}
}
return head;
}
int* findSubstring(char * s, char** words, int wordsSize, int* returnSize){
int step = strlen(words[0]); // words的字符串长度相等
int lenHash = step * wordsSize;
int lenS = strlen(s);
int* arr = (int *)malloc(sizeof(int) * lenS);
int* hash = (int*)malloc(sizeof(int) * wordsSize);
int k = 0;
HashTable* head = AddHash(words, wordsSize); // 构造哈希
HashTable* out = NULL;
for (int i = 0; i < step; ++i) { // 窗口左侧步进是一个step，所以要遍历一个step里面的左右起点
int l = i;
memset(hash, 0, sizeof(int) * wordsSize);
for (int r = i; r < lenS; r += step) { // 窗口右侧一个步进、一个步进前进
char str[step + 1];
str[0] = '\0';
strncat(str, s + r, step); // 截取一个step的字符串、查找
HASH_FIND_STR(head, str, out);
if(NULL == out) { // 未找到，就得重新归零、重新开始，移至下一个元素开头
memset(hash, 0, sizeof(int) * wordsSize); // 用hash数组代替uthash的增删；
l = r + step; // hash数组：滑动窗口中个字符串出现的次数!
} else { // 窗口中的截取串str在words中出现了，窗口内左侧的子串一定是出现在words里面的！
int idx = out->idx;
int cnt = out->cnt;
hash[idx]++; // 统计str出现的次数，hash为words的字符串各自出现在窗口中的次数；
while(hash[idx] > cnt) { // 在满足条件的结果中：一个word的次数少了，必定导致另外一个word的次数多了
char str1[step + 1];
str1[0] = '\0';
strncat(str1, s + l, step);
HASH_FIND_STR(head, str1, out);
hash[out->idx]--;
l += step;
}
if (r - l + step == lenHash) { // 窗口匹配后、窗口左侧右移一个step，并hash[idx]--;
arr[k++] = l; // 记录ans结果
char str1[step + 1];
str1[0] = '\0';
strncat(str1, s + l, step);
HASH_FIND_STR(head, str1, out);
hash[out->idx]--;
l += step;
}
}
}
}
*returnSize = k;
return arr;
}
C代码：失败案例：哈希表保存重复出现文章来源地址https://www.toymoban.com/news/detail-433452.html
typedef struct {
char *str;
int cnt;
int idx;
UT_hash_handle hh;
} HashTable;
HashTable* AddHash(char **words, int wordsSize) {
HashTable* head = NULL;
HashTable* out = NULL;
for (int r = 0; r < wordsSize; r++) {
HASH_FIND_STR(head, words[r], out);
if(NULL == out) {
out = (HashTable*)malloc(sizeof(HashTable));
out->str = words[r];
out->cnt = 1;
out->idx = r;
HASH_ADD_STR(head, str, out);
} else {
out->cnt++;
}
}
return head;
}
int* findSubstring(char * s, char** words, int wordsSize, int* returnSize){
int step = strlen(words[0]);
int lenHash = step * wordsSize;
int lenS = strlen(s);
int* arr = (int *)malloc(sizeof(int) * lenS);
int* hash = (int*)malloc(sizeof(int) * wordsSize);
int k = 0;
HashTable* head = AddHash(words, wordsSize);
HashTable* out = NULL;
for (int i = 0; i < step; ++i) { // 遍历初始节点
int l = i;
memset(hash, 0, sizeof(int) * wordsSize);
for (int r = i; r < lenS; r += step) { // 从初始节点开始，一段一段遍历
char str[step + 1];
strncpy(str, s + r, step);
HASH_FIND_STR(head, str, out);
if(NULL == out) { // 未找到，就得重新归零、重新开始，移至下一个元素开头
memset(hash, 0, sizeof(int) * wordsSize); // 用hash数组代替uthash的增删；
l = r + step; // hash数组：滑动窗口中个字符串出现的次数!
} else {
int idx = out->idx;
int cnt = out->cnt;
hash[idx]++; // 下标出现过、hash[idx]次数
while(hash[idx] > cnt) { // 经典的滑动窗口套路，滑动窗口中个字符串出现的次数 > uthash中该字符串出现的次数
char str1[step + 1]; // 窗口就应该收缩左边！直到窗口中字符串次数满足uthash的
strncpy(str1, s + l, step);
HASH_FIND_STR(head, str1, out);
hash[out->idx]--;
l += step;
}
if (r + step - l == lenHash) { // 窗口匹配后、l右移1个step，并hash[idx]--;
arr[k++] = l; // 记录结果，l并左移一个step；
char str1[step + 1];
strncpy(str1, s + l, step);
HASH_FIND_STR(head, str1, out);
hash[out->idx]--;
l += step;
}
}
}
}
*returnSize = k;
return arr;
}
到了这里，关于30. 串联所有单词的子串【memset(hash, 0, sizeof(hash)) 这样的方式真的不要再使用、leetcode有时真的会g的】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
