LeetCode(30) Substring with Concatenation of All Words
2024-09-08 08:12:58
题目
You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).
分析
解决该问题的关键是理解清楚要求。
给定一个目标字符串s,一个单词集合words。
要求使得words集合中所有元素连续出现在s中的首位置组成的集合(元素顺序不考虑)。
正如所给实例,目标字符串s: “barfoothefoobarman”
对比单词集合words: [“foo”, “bar”]
我们发现,在pos=0 ~ 5时“barfoo”恰好匹配,则0压入结果vector;
在pos=9 ~ 14时“foobar”恰好匹配,则9压入结果vector;
在理清楚题意后,便可入手程序实现。
AC代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (words.empty())
return vector<int>();
vector<int> ret;
//记录所给words中每个单词的出现次数
map<string, int> word_count;
//每个单词的长度相同
int word_size = strlen(words[0].c_str());
int word_nums = words.size();
//所给匹配字符串的长度
int s_len = strlen(s.c_str());
for (int i = 0; i < word_nums; i++)
++word_count[words[i]];
int i, j;
map<string, int> temp_count;
for (i = 0; i < s_len - word_nums*word_size + 1; ++i)
{
temp_count.clear();
for (j = 0; j < word_nums; j++)
{
//检验当前单词是否属于words以及出现的次数是否一致
string word = s.substr(i + j*word_size, word_size);
if (word_count.find(word) != word_count.end())
{
++temp_count[word];
//如果出现的次数与words不一致,则返回错误
if (temp_count[word] > word_count[word])
break;
}//if
else{
break;
}//else
}//for
//所有words内的单词,在i起始位置都出现,则将下标i存入结果的vector中
if (j == word_nums)
{
ret.push_back(i);
}//if
}//for
return ret;
}
};
最新文章
- Call for Papers IEEE/ACM International Conference on Advances in Social Network Analysis and Mining (ASONAM)
- T-SQL:毕业生出门需知系列(七)
- 视觉机器学习笔记------CNN学习
- Java 自动装箱与拆箱
- summary of k Sum problem and solutions in leetcode
- knockout 学习实例2 text
- HDU1568斐波那契推理
- C#:将子Form加入父Form中
- CSS中定位position
- web_profile(网站分析)配置
- OpenWrt for vmware 从openwrt.org下载10.03.1 或是自己下载最新的源码进行编译生成x86 vmdk格式
- CQRS模式实现
- python 读取文件时报错UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0x80 in position 205: illegal multibyte sequence
- 详解mybatis映射配置文件
- [译]ASP.NET Core揭秘 - Razor Pages
- 单模式串匹配----浅谈kmp算法
- 使用指针来实现变长数组(VLA)
- mybatis拦截器处理
- 微信小程序 - setData:key的几种用法
- 20155309 《Java程序设计》实验三(Java面向对象程序设计)实验报告