[力扣_30] 串联所有单词的子串

前言:恕我愚笨,对数据结构的欠缺和理解,并不能想出最优的解法,琢磨了很多天依旧不懂思路,以下解法是我能想到最好的解法了。

img

相关算法:

  • Hash,滑动窗口,时间复杂度O(ns)(单词长度字符串长度),空间复杂度O(n)两个Hash的长度

首先,最直接的思路,判断每个子串是否符合,符合就把下标保存起来,最后返回即可。

img

如上图,利用循环变量 i ,依次后移,判断每个子串是否符合即可。

怎么判断子串是否符合?这也是这个题的难点了,由于子串包含的单词顺序并不需要固定,如果是两个单词 A,B,我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A,B,C 也还好,只需要判断子串是否是 ABC,或者 ACB,BAC,BCA,CAB,CBA 就可以了,但如果更多单词呢?那就崩溃了。

用两个 HashMap 来解决。首先,我们把所有的单词存到 HashMap 里,key 直接存单词,value 存单词出现的个数(因为给出的单词可能会有重复的,所以可能是 1 或 2 或者其他)。然后扫描子串的单词,如果当前扫描的单词在之前的 HashMap 中,就把该单词存到新的 HashMap 中,并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ,如果大了,就代表该子串不是我们要找的,接着判断下一个子串就可以了。如果不大于,那么我们接着判断下一个单词的情况。子串扫描结束,如果子串的全部单词都符合,那么该子串就是我们找的其中一个。看下具体的例子。

看下图,我们把 words 存到一个 HashMap 中。

img

然后遍历子串的每个单词。

img

第一个单词在 HashMap1 中,然后我们把 foo 存到 HashMap2 中。并且比较此时 foo 的 value 和 HashMap1 中 foo 的 value,1 < 2,所以我们继续扫描。

img

第二个单词也在 HashMap1 中,然后把 foo 存到 HashMap2 中,因为之前已经存过了,所以更新它的 value 为 2 ,然后继续比较此时 foo 的 value 和 HashMap1 中 foo 的 value,2 <= 2,所以继续扫描下一个单词。

img

第三个单词也在 HashMap1 中,然后把 foo 存到 HashMap2 中,因为之前已经存过了,所以更新它的 value 为 3,然后继续比较此时 foo 的 value 和 HashMap1 中 foo 的 value,3 > 2,所以表明该字符串不符合。然后判断下个子串就好了。

当然上边的情况都是单词在 HashMap1 中,如果不在的话就更好说了,不在就表明当前子串肯定不符合了,直接判断下个子串就好了。

代码如下所示:

/**
 * Note:
  The returned array must be malloced, assume caller calls free().
 */
typedef struct HashNode
{
    char* key;
    int val;
    int num;//截取判断的子串中单词对应出现的次数
    struct HashNode* next;
}HashNode,*HashList;

typedef struct HashMap
{
    HashList Data;
    int HashLen;
}HashMap;
void InitHashMap(HashMap* M,int wordsSize)
{
    M->Data = (HashList)malloc(sizeof(HashNode));
    M->Data->key = NULL;
    M->Data->next = NULL;
    M->Data->num = -1;
    M->Data->val = -1;
    M->HashLen = 0;
}
void CreateHashMap(HashMap* M, char** words, int wordsSize,int sleng)
{
    HashList p = M->Data;
    HashList t = p;
    for (int i = 0; i < wordsSize; i++)
    {
        char* s = words[i];
        p=M->Data;
        t=p;
        while (p)
        {
            if(p!=M->Data)
              if(!strcmp(p->key,s)) break;
            t = p;
            p = p->next;
        }
        if (!p)
        {
            t->next = (HashList)malloc(sizeof(HashNode));
            t = t->next;
            t->val = 1;
            t->key = (char*)malloc(sizeof(char) * (sleng + 1));
            strcpy(t->key, s);
            t->num = 0;
            t->next = NULL;
            M->HashLen++;
        }
        else
            p->val++;
    }
}
int SubString(char* s, char* t, int pos, int len)
{
    if (pos + len > strlen(s)) return 0;
    int j = 0;
    for (int i = pos; i < pos + len; i++, j++)
        t[j] = s[i];
    t[j] = '\0';
    return 1;
}
int check(HashMap *M,char *s,int Wordlen)
{
    int slen=strlen(s);
    char temp[Wordlen+1];
    int i=0;
    HashList p=M->Data->next;
    int sin=0;
    while(i<slen)
    {
       SubString(s,temp,i,Wordlen);//从字串中截取单词
       p=M->Data->next;
       while(p)
       {
           if(!strcmp(temp,p->key)&&p->num < p->val)
           {     
               p->num++;
               sin=1;
           }
            p=p->next;
       }
       if(!sin) return 0;
       i+=Wordlen;
    }
    int sign=1;
    HashList t=M->Data->next;
    while(t)判断是否全部满足
    {
        if(t->val!=t->num)
            sign=0;
        t->num=0;//出现次数清0
        t=t->next;
    }
    t=M->Data->next;
    return sign;
}
int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
    *returnSize = 0;
    if(!wordsSize||!words||!s) return NULL;
    int sleng = strlen(s);//字符串总长度
    int* res=(int*)malloc(sizeof(int)*sleng);
    int len = strlen(words[0]);//单个单词长度
    if(sleng<len) return NULL;
    int TotalLen = len * wordsSize;//所有单子长度
    int p = 0;
    char* temp = (char*)malloc(sizeof(char) * (TotalLen + 1));
    
    HashMap M;
    
    InitHashMap(&M, wordsSize);
    
    CreateHashMap(&M, words, wordsSize, sleng);

    for (int i = 0; i < sleng;i++)
    {
        if (SubString(s, temp, i, TotalLen))
        {
            if(check(&M,temp,len))
            {   
                res[*returnSize]=i;
                (*returnSize)++;
            }
        }
    }
    return res;
}

本文链接:

https://nullcode.fun/77.html
1 + 9 =
快来做第一个评论的人吧~