leetcode - [30. 串联所有单词的子串]

zz/2024/5/21 21:18:38
leetcode - [30. 串联所有单词的子串]

题目大意

给定一个源字符串 s,再给一个字符串数组,要求在源字符串中找到由字符串数组各种组合组成的连续串的起始下标,如果存在多个,在结果中都需要输出。

解题思路

这一题看似很难,但是有 2 个限定条件也导致这题不是特别难。1. 字符串数组里面的字符串长度都是一样的。2. 要求字符串数组中的字符串都要连续连在一起的,前后顺序可以是任意排列组合。

解题思路,先将字符串数组里面的所有字符串都存到 map 中,并累计出现的次数。然后从源字符串从头开始扫,每次判断字符串数组里面的字符串时候全部都用完了(计数是否为 0),如果全部都用完了,并且长度正好是字符串数组任意排列组合的总长度,就记录下这个组合的起始下标。如果不符合,就继续考察源字符串的下一个字符,直到扫完整个源字符串。

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
vector<int> findSubstring(string S, vector<string> &L)
{vector<int> result;if (S.size() <= 0 || L.size() <= 0){return result;}int n = S.size(), m = L.size(), l = L[0].size();//将所有单词放入map中map<string, int>expected;for (int i = 0; i < m; i++){if (expected.find(L[i]) != expected.end()){expected[L[i]]++;}else{expected[L[i]] = 1;}}for (int i = 0; i < l; i++){map<string, int>actual;int count = 0;//总数int winLeft = i;for (int j = i; j <= n - 1; j += l){string word = S.substr(j, l);//如果没有找到,则从j+1重新开始;if (expected.find(word) == expected.end()){actual.clear();count = 0;winLeft = j + l;continue;}count++;//计算“单词”的数量if (actual[word] > expected[word]){string tmp;do{count--;actual[tmp]--;winLeft += l;}while (tmp != word);}// 如果总计数等于 L 的大小,则找到一个结果if (count == m){result.push_back(winLeft);string tmp = S.substr(winLeft, l);actual[tmp]--;winLeft += l;count--;}}}return result;
}int main(int argc, char **argv)
{string s = "barfoobarfoothefoobarman";vector<string> l;l.push_back("foo");l.push_back("bar");l.push_back("foo");vector<int> indics = findSubstring(s, l);for (int i = 0; i < indics.size(); i++){cout << indics[i] << ".";}cout << endl;return 0;
}

http://www.ngui.cc/zz/2727423.html

相关文章

leetcode - [35. 搜索插入位置]

leetcode - [35. 搜索插入位置] 题目大意 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 解题思路 给出一个已经从小到大排序…

c++高级编程学习笔记3

函数指针的类型别名 我们通常不考虑函数在内存中的位置&#xff0c;但每个函数实际上都位于某个特定地址。在 C中&#xff0c;可像使用数据那样使用函数。换言之&#xff0c;可使用函数的地址&#xff0c;就像使用变量那样。函数指针的类型取决于兼容函数的参数类型的返回类型…

Qt例子学习笔记 - Examples/Qt-6.2.0/qt3d/basicshapes-cpp

main.cpp //基本形状显示了 Qt 3D 提供的四种基本形状&#xff1a;圆环、圆柱、立方体和球体。 //该示例还展示了如何将 Qt 3D 场景嵌入到小部件中并与其他小部件连接。#include "scenemodifier.h"#include <QGuiApplication> #include <Qt3DRender/qcame…

Qt例子学习笔记 - Examples/Qt-6.2.0/assistant/simpletextviewer

main.cpp #include "mainwindow.h"#include <QApplication> //QApplication 专门为 QGuiApplication 提供了一些基于 QWidget 的应用程序所需的功能。 // 它处理特定于小部件的初始化、完成。 //对于任何使用 Qt 的 GUI 应用程序&#xff0c;无论应用程序在任…

Qt例子学习笔记 - Examples/Qt-6.2.0/charts/customchart

//自定义图表 //我们首先创建一个简单的线系列和一个图表对象。 QLineSeries *series new QLineSeries();*series<<QPointF(0,6)<<QPointF(9,4)<<QPointF(15,20) << QPointF(25, 12) << QPointF(29, 26);QChart *chart new QChart();chart->…

跨平台编译项目

1.linux:INCLUDEPATH “” 2.linux: { message(linux) } 3.message($$QMAKESPAEC) xzxiaqiu:~/study/csdn/day0/test/build$ ls /opt/Qt/Qt6/6.2.0/gcc_64/mkspecs/ aix-g integrity-x86 macx-clang solaris-cc-64 aix-g-64 linux…

布局Layout

布局Layout 1.Vertical Layout 2.Horizontal Layout 3.Grid Layout 4.Form LayoutsizeHint推荐尺寸 1.QSize sizeHint() 推荐尺寸只能重载修改 2.QSize size() 不包含边框的窗口尺寸QSizePolicy::PolicyFlag 1.GrowFlag 必要时可超过推荐 2.ExpandFlag 尽可能的扩展 3.ShrinkF…

QTreeWidgetQTreeWidget

QTreeWidget 1.常用属性 2.标题设置 3.内容插入 4.内容选择 5.拖动和删除 6.信号事件 7.样式qss QTreeWidget 属性 1.header()->setVisible(true) 2.setSortingEnabled点击标题排序 3.setAnimated 动画展开 4.setVerticalScrollBarPolicy setHorizontalScrollBarPolicy滚动…

JDK 和 JRE 的区别

JRE(Java Runtime Enviroment) 是 Java 的运行环境。面向 Java 程序的使用者&#xff0c;而不是开发者。如果你仅下载并安装了JRE&#xff0c;那么你的系统只能运行 Java 程序。JRE 是运行 Java 程序所必须环境的集合&#xff0c;包含JVM标准实现及 Java 核心类库。它包括 Java…

通信__协议的那点事!!

我们的“协议”&#xff1a; 到目前为止&#xff0c;我们已经简单了解了通信的基本模型&#xff0c;Server—Client模型&#xff0c;这里以简单聊天工具为例&#xff1a;1、服务端启动——2、客户端启动&#xff0c;并试图与服务端建立连接——3、服务端根据条件&#xff08;通…