【算法专题突破】滑动窗口 - 串联所有单词的子串(15)

简介: 【算法专题突破】滑动窗口 - 串联所有单词的子串(15)

1. 题目解析

题目链接:30. 串联所有单词的子串 - 力扣(LeetCode)

这道题其实也很好理解,看一下示例就基本知道是什么意思了,

主要就是找 s 里面有没有我们能拼接的子串,然后返回索引即可。

2. 算法原理

我们可以把它给的子串数组中的子串看成一个个字符,

把目标子串 s 中的每一个等长子串也看成一个个字符,

我们就会发现这道题就转化成了之前我们做的那道字母异位词的题目,

我们再使用同样的思路作答即可:

3. 代码编写

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> win;
        for(auto& e : words) win[e]++;
        int len = words[0].size(), m = words.size();
        for(int i = 0; i < len; i++) {
            unordered_map<string, int> hash;
            for(int left = i, right = i, count = 0; right + len <= s.size(); right += len) {
                string in = s.substr(right, len);
                hash[in]++;
                if(hash[in] <= win[in]) count++;
                if(right - left + 1 > len * m) {
                    string out = s.substr(left, len);
                    if(hash[out] <= win[out]) count--;
                    hash[out]--;
                    left += len;
                }
                if(count == m) ret.push_back(left);
            }
        }
        return ret;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章
|
5月前
|
算法
【算法】滑动窗口——最大连续1的个数
【算法】滑动窗口——最大连续1的个数
|
1月前
|
算法
|
5月前
|
算法
【算法】滑动窗口——最小覆盖子串
【算法】滑动窗口——最小覆盖子串
|
5月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
5月前
|
算法
【算法】滑动窗口——将x减到0的最小操作数
【算法】滑动窗口——将x减到0的最小操作数
|
5月前
|
算法 容器
【算法】滑动窗口——串联所有单词的子串
【算法】滑动窗口——串联所有单词的子串
|
5月前
|
算法
【算法】滑动窗口——水果成篮
【算法】滑动窗口——水果成篮
|
12天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
12天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
108 68
|
21天前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。