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

恬静的小魔龙 发表于 2022/07/28 23:54:57 2022/07/28
【摘要】 推荐阅读 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。