30. 串联所有单词的子串【 力扣(LeetCode) 】

2024-08-20 17:28

本文主要是介绍30. 串联所有单词的子串【 力扣(LeetCode) 】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目描述

给定一个字符串 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 由小写英文字母组成

三、解题思路

  1. 基本思路:
      多层滑动窗口
  2. 具体思路:
    • 定义:ans 用于存放答案;use 用于存放 words 中单词出现的频率;use_temp 表示在每一层滑动窗口中初始的单词频率,初始化为 uselen 表示每个单词长度;c 表示单词数量;n 表示字符串长度
    • 遍历层数:第 i 层表示从 i 个字符开始,由 len 个字符组成的单词序列,小于 len 长度则舍弃。【例如 len=3,字符串为 "abcdefghij" ,则第 1 层表示 bcdefghij 三个单词,第 2 层表示 cdefgh 两个单词】
    • 每层的滑动窗口:定义变量 startend 表示首单词和尾单词。每次变量该层的单词序列,在滑动窗口的尾部加入一个单词,判断该单词是否还有剩余的频率,有则频率 -1 ,如果为 0 ,则删去 ;没有则滑动窗口从头部开始舍弃单词,每舍弃一个单词,该单词频率 +1 ,一直丢弃到 尾部单词有空位 或 者滑动窗口为空 为止。一旦每层的单词频率 use_temp 为空,则表示所有单词都用到了,则把首单词的下标加入到答案中。
      use_temp 为空可以保证滑动窗口内所有单词都是由 words 的单词组成的,证明:如果不是,那么存在两种情况,一是出现了 words 里面没有出现的单词,二是出现了 words 里面有的单词,但是频率超了;
      • 对于第一种情况来说:出现了不存在的单词,use_temp 里面没有该单词的频率,就会进行从头部舍弃单词,一直舍弃到该单词有空位,而该单词有空位的情况是不可能满足的,所以会一直舍弃到滑动窗口为空为止,所以该单词也会被舍弃。
      • 对于第二种情况来说,一旦频率不够,就会进行舍弃,所以不可能会出现滑动窗口里面的单词频率超过的可能。】
    • 返回结果 ans

四、参考代码

时间复杂度: O ( n ∗ l e n ) \Omicron(n*len) O(nlen) 字符串长度 * 层数
空间复杂度: O ( c ∗ l e n ) \Omicron(c*len) O(clen) map 的空间

class Solution {
public:map<string, int> init(vector<string> words) {int n = words.size();map<string, int> ans;for (int i = 0; i < n; i++) ans[words[i]]++;return ans;}vector<int> findSubstring(string s, vector<string>& words) {int n = s.length();int c = words.size(), len = words[0].length();vector<int> ans;map<string, int> use = init(words);for (int i = 0; i < len; i++) {map<string, int> use_temp = use;for (int j = i, k = i; k < n;) {string end = s.substr(k, len);string start = s.substr(j, len);if (use_temp.count(end) == 1) {use_temp[end]--;if (use_temp[end] == 0)use_temp.erase(end);k += len;} else {while (start != end && j <= k) {use_temp[start]++;start = s.substr(j += len, len);}j += len;k += len;}if (use_temp.empty()) {ans.push_back(j);}}}return ans;}
};

这篇关于30. 串联所有单词的子串【 力扣(LeetCode) 】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1090706

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

30常用 Maven 命令

Maven 是一个强大的项目管理和构建工具,它广泛用于 Java 项目的依赖管理、构建流程和插件集成。Maven 的命令行工具提供了大量的命令来帮助开发人员管理项目的生命周期、依赖和插件。以下是 常用 Maven 命令的使用场景及其详细解释。 1. mvn clean 使用场景:清理项目的生成目录,通常用于删除项目中自动生成的文件(如 target/ 目录)。共性规律:清理操作

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点