首页 > 其他分享 >30. 串联所有单词的子串

30. 串联所有单词的子串

时间:2023-11-06 17:12:56浏览次数:36  
标签:子串 串联 int 30 单词 len1 sublen words

给定一个字符串 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] 也是可以的。

代码


class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        const int len = words.size();
        const int len1 = words[0].size();
        int sublen = len*len1;
        if(s.size() < sublen) return {};

        for(auto& word:words){
            mymap[word]++;
        }

        vector<unordered_map<string, int> > vu(len1);
        for(int i = 0;i < len1;i++){
            for(int j = i; j < i + sublen;j += len1){
                string s_sub = s.substr(j,len1);
                vu[i][s_sub]++;
            }
            if(vu[i] == mymap){
                res.emplace_back(i);
            }
        }
        // sliding window: 滑动窗口,每次移动 d 个位置
        for(int i = len1;i + sublen <= s.size(); i++){
            int r = i % len1;
            string wa = s.substr(i - len1, len1), wb = s.substr(i + sublen - len1, len1);
            if(--vu[r][wa] == 0) vu[r].erase(wa);
            vu[r][wb]++;
            if (vu[r] == mymap) {
                res.emplace_back(i);
            }
        }
        return res;
    }
private:
    unordered_map<string,int> mymap;
    vector<int> res;
};

标签:子串,串联,int,30,单词,len1,sublen,words
From: https://www.cnblogs.com/lihaoxiang/p/17813158.html

相关文章

  • 报错:1130-host ... is not allowed to connect to this MySql server 开放mysql远程
    报错:1130-host...isnotallowedtoconnecttothisMySqlserver开放mysql远程连接不使用localhost解决方法:1。改表法。可能是你的帐号不允许从远程登陆,只能在localhost。这个时候只要在localhost的那台电脑,登入mysql后,更改"mysql"数据库里的"user"表里的"host"项,从"......
  • 上周热点回顾(10.30-11.5)
    热点随笔:· 张良计诉园子侵权案一审结束:需7天内证明转载博文是用户发布 (博客园团队)· 开源2年、打磨13年、300万行代码的开源项目 (削微寒)· 用1100天做一款通用的管理后台框架 (胡尐睿丶)· C#/.NET/.NETCore优秀项目和框架2023年10月简报 (追逐时光者)· 记......
  • 2023-2024-1 20231304 《计算机基础与程序设计》第六周学习总结
    2023-2024-120231304《计算机基础与程序设计》第六周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第六周作业这个作业的目标作业正文2023-2024-120231304《计算机基础与程......
  • 2023-2024-1 20231305 《计算机基础与程序设计》第六周学习总结
    2023-2024-1学号:20231305《计算机基础与程序设计》第六周学习总结作业信息这个作业属于哪个课程<班级的链接>(如2022-2023-1-计算机基础与程序设计)这个作业要求在哪里<作业要求的链接>(如2022-2023-1计算机基础与程序设计第六周作业)这个作业的目标<自学教材计算......
  • 2023-2024-1 20231307《计算机基础与程序设计》第六周学习总结
    作业信息所属课程2023-2024-1-计算机基础与程序设计作业要求在哪里2023-2024-1计算机基础与程序设计第六周作业作业目标学习教材《计算机科学概论》第7章《C语言程序设计》第5章并完成云班课测试作业正文https://www.cnblogs.com/lzt-/p/17811272.html教材......
  • 2023-2024-1 20231301 《计算机基础与程序设计》第六周学习总结
    2023-2024-120231301《计算机基础与程序设计》第六周学习总结作业信息作业链接作业课程<班级>(2023-2024-1-计算机基础与程序设计)作业要求<作业>(2023-2024-1计算机基础与程序设计第六周学习总结)作业目标<《计算机基础与程序设计》预习第七章>《计算机基础......
  • 2023-2024-1 20231306 《计算机基础与程序设计》第六周学习总结
    这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第六周作业这个作业的目标Polya如何解决问题、简单类型与组合类型、复合数据结构、查找与排序算法、算法复杂度、递归、代码安全作业正文《计算机......
  • 2023-2024-1 20231309 《计算机基础与程序设计》第六周学习总结
    2023-2024-120231309《计算机基础与程序设计》第六周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里2023-2024-1计算机基础与程序设计第六周作业这个作业的目标作业正文2023-2024-120231309《计算机基础与程......
  • 大二快乐日记10.30
    MySQL的数据类型有大概可以分为5种,分别是整数类型、浮点数类型和定点数类型、日期和时间类型、字符串类型、二进制类型等。注意:整数类型和浮点数类型可以统称为数值数据类型。1)数值类型整数类型包括TINYINT、SMALLINT、MEDIUMINT、INT、BIGINT,浮点数类型包括FLOAT和DOUB......
  • 2023-2024-1 20231303 《计算机基础与程序设计》赵泊瑄第六周学习总结
    2023-2024-120231303《计算机基础与程序设计》赵泊瑄第六周学习总结作业信息这个作业属于哪个课程2023-2024-1-计算机基础与程序设计这个作业要求在哪里作业要求的链接2023-2024-1计算机基础与程序设计第六周作业)这个作业的目标总结第六周学习收获作业正文......