LeetCode50天刷题计划（Day 3—— 串联所有单词的子串 10.00-13.20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

写难题还是自不量力 害

一、题目描述

题目

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

提示：

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

二、思路

目前看懂的题解都是用固定的窗口长度，每次滑动一个字母，将窗口字符串按照单词定长进行分割，然后用哈希表统计分割后单词出现的次数，与提前维持好的哈希表进行比对
我一开始的思路是用变长的窗口，每次比对失败时或出现某个问题时向前滑动，但是太菜了很多细节现在考虑不清楚 希望有朝一日可以回来把这个写完
以后还是以中等题为主吧 困难题真塔喵的不想再碰了QAQ

三、代码

1.有问题的代码（python）

from collections import Counter

class Solution(object):
    def findSubstring(self, s, words):
        """ :type s: str :type words: List[str] :rtype: List[int] """
        #本题采用滑动窗口解题，但是窗口移动大小是单词长度
        move=len(words[0])

        #维持一个hash表
        count=Counter(words)

        #放置本轮元素的hash表
        cur=Counter()
        for i in list(count.keys()):
            cur[i]=0
       
        #指向窗口前端的指针
        front=0
        #返回结果
        return_list=[]
        #移动 【先假设字符串正好是长度的整倍数】
        for i in range(len(s)//move):
            #本轮单词
            temp=s[i*move:(i+1)*move]
            print(temp)#######
            #需要保证此单词在列表中
            if(temp not in words):
                front+=move
                continue
            #先移动窗口到合适的位置,使本轮单词可以插入
            while(cur[temp] >= count[temp]):
                if(front+move<len(s)): 
                    cur[s[front:(front+move)]]-=1
                    front+=move
                print(cur)#######
            #插入本轮单词
            cur[temp]+=1
            print(cur)#######
            #插入后满足长度要求，添加返回值
            if(self.judge(count,cur)):
                return_list.append(front)
                print(return_list)######
        return return_list
    
    #判断两个哈希表是否相同
    def judge(self,count,cur):
        flag=0
        for i in list(count.keys()):
            if(count[i]!=cur[i]):
                flag=1
                break
        if(flag != 1):
            return True
        else:
            return False

a=Solution()
a.findSubstring("barfoothefoobarman", ["foo","bar"])

2.python的AC

class Solution(object):
    def findSubstring(self, s, words):
        """ :type s: str :type words: List[str] :rtype: List[int] """
        #本题采用定长滑动窗口解题，窗口大小是单词长度*word中的单词数量
        n=len(s)
        word_size=len(words[0])
        win_size=word_size*len(words)
        return_list=[]

        #维持一个hash表
        count=Counter(words)

        #开始遍历
        for i in range(len(s)-win_size+1):
            #本轮窗口字符串
            win=s[i:(i+win_size)]
            #本轮分割后的单词列表（之后做成hash表）
            cur=[]
            #生成列表
            for j in range(0,win_size,word_size):
                cur.append(win[j:j+word_size])
            #生成hash表并比较
            if Counter(cur) == count:
                return_list.append(i)
        return return_list