☆打卡算法☆LeetCode 30、串联所有单词的子串 算法解析

-打卡算法-LeetCode 30、串联所有单词的子串 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个单词数组，匹配另一个数组中是否存在这个单词数组中所有的串联单词，返回起始位置。”

题目链接：

来源：力扣（LeetCode）

链接：​​30. 串联所有单词的子串 - 力扣（LeetCode） (leetcode-cn.com)​​

2、题目描述

给定一个字符串 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、思路分析

这个题可以采用滑动窗口的思想解题。

因为单词长度是固定的，我们可以维护一个所有单词长度总和的长度队列。

然后在字符串中进行遍历查找。

2、代码实现

代码参考：

public class Solution { public IList FindSubstring(string s, string[] words) { IList result=new List(); //窗口宽度 var wl=words[0].Count(); var wc=words.Count(); var wtl=wl*words.Count(); //总长 var sl=s.Count(); for(int i=0;i

3、时间复杂度

时间复杂度 ： O(n)

其中n代表单词长度。

空间复杂度： O(1)

只需要常数级个变量。

三、总结

代码还可以多加一些判断，让算法更加优化。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。