LeetCode 算法:找到字符串中所有字母异位词c++

2024-06-02 20:20

本文主要是介绍LeetCode 算法:找到字符串中所有字母异位词c++,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接🔗:找到字符串中所有字母异位词
难度:中等⭐️⭐️

题目

给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。

示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

提示:
1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

题解

滑动窗口法

  1. 题解
  • 理解异位词:两个字符串是异位词,意味着它们包含相同的字符,并且每个字符出现的次数也相同,但是字符的排列顺序可以不同。

  • 滑动窗口:使用滑动窗口的方法来遍历字符串 s,窗口的大小与字符串 p 的长度相等。

  • 字符计数:使用哈希表(unordered_map)来记录字符串 p 中每个字符的出现次数。

  • 窗口内字符匹配:在滑动窗口的过程中,使用另一个哈希表来记录当前窗口内的字符及其出现次数,并与 p 中的字符计数进行比较。

  • 更新窗口:每次向右移动窗口时,添加新的字符到窗口的哈希表中,并从窗口中移除一个字符。

  • 判断异位词:如果在某个时刻,当前窗口内的字符计数与 p 中的字符计数相匹配,则说明找到了一个异位词,记录此时窗口的起始索引。

  • 继续滑动:继续滑动窗口直到遍历完整个字符串 s。

  • 返回结果:返回所有找到的异位词子串的起始索引列表。

  1. 复杂度:时间复杂度 O(n * m),空间复杂度 O(m)。
  2. 代码过程
  • 初始化一个哈希表 pCount 来存储 p 中字符的出现次数。

  • 初始化两个指针 left 和 right,分别指向当前考虑的窗口的起始和结束位置。

  • 使用一个哈希表 windowCount 来存储当前窗口内的字符计数。

  • 扩展窗口,直到窗口的大小等于 p 的长度。

  • 当窗口大小等于 p 的长度时,检查当前窗口是否是 p 的异位词:

    • 如果是,记录下 left 指针的位置,因为这是子串的起始索引。
    • 移动 right 指针来扩展窗口,并更新 windowCount。
  • 移动left 指针来收缩窗口,并更新 windowCount。

  • 重复步骤 5 和 6,直到 right 指针遍历完整个字符串 s。

  • 返回记录的所有起始索引。

  1. c++ demo
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>class Solution {
public:std::vector<int> findAnagrams(const std::string& s, const std::string& p) {std::vector<int> result;if (s.size() < p.size()) return result; // 如果s的长度小于p的长度,不可能有异位词// 用于存储p中字符的频率std::unordered_map<char, int> pFreq;for (char c : p) {pFreq[c]++;}// 用于存储当前窗口的字符频率std::unordered_map<char, int> windowFreq;int left = 0, right = 0; // 左右指针,定义当前窗口int validChars = 0; // 当前窗口中与p中字符匹配的字符数量// 窗口大小小于p时,继续扩展窗口while (right < s.size() && right - left < p.size()) {char c = s[right];if (pFreq.find(c) != pFreq.end()) {windowFreq[c]++;}right++;}// 当窗口大小等于p时,开始检查是否为异位词while (right - left == p.size()) {// 如果当前窗口是p的异位词,记录起始索引if (isAnagram(pFreq, windowFreq)) {result.push_back(left);}// 移动窗口char leftChar = s[left];if (pFreq.find(leftChar) != pFreq.end()) {if (windowFreq[leftChar] == pFreq[leftChar]) {validChars--;}windowFreq[leftChar]--;if (windowFreq[leftChar] < pFreq[leftChar]) {validChars++;}}left++;// 扩展窗口if (right < s.size()) {char rightChar = s[right];if (pFreq.find(rightChar) != pFreq.end()) {windowFreq[rightChar]++;if (windowFreq[rightChar] == pFreq[rightChar]) {validChars--;}}right++;}}return result;}private:// 辅助函数,用于比较两个字符计数映射是否相等bool isAnagram(const std::unordered_map<char, int>& pFreq,const std::unordered_map<char, int>& windowFreq) {for (const auto& kv : pFreq) {if (kv.second != windowFreq.at(kv.first)) {return false;}}return true;}
};int main() {Solution solution;std::string s = "cbaebabacd";std::string p = "abc";std::vector<int> anagramIndices = solution.findAnagrams(s, p);std::cout << "Start indices of anagrams of \"" << p << "\" in \"" << s << "\" are:" << std::endl;for (int index : anagramIndices) {std::cout << index << std::endl;}return 0;
}
  • 输出结果:

Start indices of anagrams of “abc” in “cbaebabacd” are:
0
6
在这里插入图片描述

这篇关于LeetCode 算法:找到字符串中所有字母异位词c++的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1024992

相关文章

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳:精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

python修改字符串值的三种方法

《python修改字符串值的三种方法》本文主要介绍了python修改字符串值的三种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录第一种方法:第二种方法:第三种方法:在python中,字符串对象是不可变类型,所以我们没办法直接

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

深入理解C++ 空类大小

《深入理解C++空类大小》本文主要介绍了C++空类大小,规定空类大小为1字节,主要是为了保证对象的唯一性和可区分性,满足数组元素地址连续的要求,下面就来了解一下... 目录1. 保证对象的唯一性和可区分性2. 满足数组元素地址连续的要求3. 与C++的对象模型和内存管理机制相适配查看类对象内存在C++中,规

C#中字符串分割的多种方式

《C#中字符串分割的多种方式》在C#编程语言中,字符串处理是日常开发中不可或缺的一部分,字符串分割是处理文本数据时常用的操作,它允许我们将一个长字符串分解成多个子字符串,本文给大家介绍了C#中字符串分... 目录1. 使用 string.Split2. 使用正则表达式 (Regex.Split)3. 使用