LeetCode-30 串联所有单词的子串

简介: LeetCode-30 串联所有单词的子串

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words

题目描述

给定一个字符串 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 <= s.length <= 104
s 由小写英文字母组成
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 由小写英文字母组成

解题思路

题目中重点强调了长度相同,这就是解题的关键,由于长度相同,我们完全可以知道子串的长度就是单个单词长度乘以单词个数,所以可以使用一个子串长度的滑动窗口,依次判断各个起始位置的滑动窗口内子串是否符合题目要求。

同样由于单词长度固定已知,可以直接将窗口内的子串拆解成一个一个单词判断是否在words数组内,为了提高速度,可以把words数组内的单词存入一个哈希表。

代码展示

 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> viRet;
        unordered_map<string, int> striMap, strimapTemp;
        for(auto word: words)
        {
            striMap[word]++;
        }
        int iLen = words.size() * words[0].size();
        for(int i = 0; i < s.size() - iLen + 1; i++)
        {
            strimapTemp = striMap;
            bool bTemp = true;
            for(int j = 0; j < words.size(); j++)
            {
                string word = s.substr(i + j * words[0].size(), words[0].size());
                if(strimapTemp[word] == 0)
                {
                    bTemp = false;
                    break;
                }
                strimapTemp[word]--;
            }
            if(bTemp)
                viRet.push_back(i);
        }
        return viRet;
    }
};

运行结果

 

相关文章
|
2月前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
20 0
|
2月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
19 0
|
4月前
|
算法
LeetCode第58题最后一个单词的长度
LeetCode第58题"最后一个单词的长度"的解题方法,通过从字符串末尾向前遍历并计数非空格字符,直接得出最后一个单词的长度。
LeetCode第58题最后一个单词的长度
|
4月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
46 4
|
4月前
|
Python
【Leetcode刷题Python】生词本单词整理
文章提供了一个Python程序,用于帮助用户整理和排版生词本上的单词,包括去除重复单词、按字典序排序,并按照特定的格式要求进行打印排版。
42 3
|
4月前
|
Python
【Leetcode刷题Python】318. 最大单词长度乘积
本文提供了LeetCode题目318的Python编程解决方案,题目要求在一个字符串数组中找出两个不含有公共字母的单词,且这两个单词的长度乘积最大,如果不存在这样的两个单词,则返回0。
21 0
|
6月前
|
存储 算法 测试技术
力扣经典150题第三十三题:最小覆盖子串
力扣经典150题第三十三题:最小覆盖子串
39 1
|
6月前
|
算法 测试技术 索引
力扣经典150题第三十二题:串联所有单词的子串
力扣经典150题第三十二题:串联所有单词的子串
28 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2