☆打卡算法☆LeetCode 30、串联所有单词的子串 算法解析
【摘要】
推荐阅读
CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不...
推荐阅读
大家好,我是小魔龙,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] 也是有效答案。
- 1
- 2
- 3
- 4
- 5
- 6
示例 2:
输入: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出: []
- 1
- 2
- 3
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
- 1
- 2
- 3
二、解题
1、思路分析
这个题可以采用滑动窗口的思想解题。
因为单词长度是固定的,我们可以维护一个所有单词长度总和的长度队列。
然后在字符串中进行遍历查找。
2、代码实现
代码参考:
public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
IList<int> result=new List<int>();
//窗口宽度
var wl=words[0].Count();
var wc=words.Count();
var wtl=wl*words.Count();
//总长
var sl=s.Count();
for(int i=0;i<sl-wtl+1;i++){
var t=s.Substring(i,wtl);
//Test for whether these words can combine the substring
if(Test(t)){
result.Add(i);
}
}
return result;
bool Test(string ss){
string[] temp=new string[wc];
words.CopyTo(temp,0);
for(int j=0;j<wc;j++){
var w=ss.Substring(j*wl,wl);
var flag=0;
for(int k=0;k<wc;k++){
if(temp[k]==w){
temp[k]="";
flag=1;
break;
}
}
if(flag==0) return false;
}
return true;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
3、时间复杂度
时间复杂度 : O(n)
其中n代表单词长度。
空间复杂度: O(1)
只需要常数级个变量。
三、总结
代码还可以多加一些判断,让算法更加优化。
文章来源: itmonon.blog.csdn.net,作者:恬静的小魔龙,版权归原作者所有,如需转载,请联系作者。
原文链接:itmonon.blog.csdn.net/article/details/126039250
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)