LeetCode: 30. Substring with Concatenation of All Words

引言

题目链接:https://leetcode.com/problems/substring-with-concatenation-of-all-words/

题目大意

给出一个长字符串s和一个字符串数组words,返回由words中字符串拼接成的长字符串(假设为x)在s中的索引集合(x由words中所有元素拼接而成,每一个元素都包含且只有一个)

Hint

------------------
1. words中的每个字符串长度相等
2. words中的字符串可以重复(自己脑补了一波,坑skr人T_T)

  • Example

题解

这个题目其实和LeetCode的第三题Substring Without Repeating Characters的解题思路核心是一样的,可以看看博主之前的题解 传送门 Click Here!都是利用滑动窗口的思想。

来分析下两道题题目的区别,第三题求的是连续的最长的不包含重复字符的子串长度,这道题目求解由words中字符串拼接成的长字符串x在s中的索引位置集合。转换一下,就是s中查找连续的一段字符串x,这个字符串由words中所有字符串拼接而成,把所有符合条件的索引记录返回即可。 所以两者本质上是一致的。

由于本题words中所有字符串长度一致(假设为len),所以可以把len当做一个整体。设定滑动窗口包含的子串由words中单词拼接而成(当前从某个起点开始正在查询并且不断扩展的子串),采取如下步骤解题

  1. 申明一个hashmap,用words中的字符串作为key在words中出现次数作为value,构建比对映射表。
  2. 设定当前滑动窗口左边界lastDiffIndex,初始为0
  3. 申明一个curhashmap表示已经匹配查询列表,查询长度为len的子串sub在hashmap中是否存在
    1. 不存在:表明当前滑动窗口不符合规范,不能由words中所有字符串凭拼接构成,直接设置滑动窗口左边界为当前下标
    2. 存在:(1)curhashmap中的键值对对应数量小于hashmap查询子串有效,滑动窗口左边界不变对应curhashmap对应键值数量加一,继续查询下一个长度为len的子串sub,(2)curhashmap中的键值对对应数量大于等于hashmap查询子串,无效,移动滑动窗口左边界每次加len的跨度,知道当前查询子串sub对应键值数量小于等于hashmap

这样可以做到每次跨度为words中单个字符串长度len,为了能够遍历到所有单词组合,一般来说会选择双层循环外层每次+1再次遍历,但是本题words中字符串长度一致,每次跨度都是len,所以只需要+1往后偏移len-1次进行跨度为len的完全遍历即可覆盖s中的所有字符,因为再次偏移到len实际上已经进入了下一个周期循环完全重复。

因此本题采用双层循环,外层i = [0-len]跨度为1,内层j = [i, lens-len]跨度为len,每次截取长度为[j,j+len]之间的字符串判断,总遍历次数 为 len*n/len=n

复杂度

时间复杂度 O(n)

空间复杂度 O(km),k为给出的单词序列的长度,m为序列中每个单词的长度

AC代码

c++版本

go版本

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论