Substring with Concatenation of All Words
问题描述： 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”]
【LeetCode|30.查找所有可能的字符串组合】You should return the indices: [0,9].
(order does not matter).
知识补充： unordered_map
unordered_map c;
//分别对应键的类型和键值的类型
c[0] = 1;
//简单的插入数据形式
c.find(key)==c.end();
//判断无序图内是否有这个键
c.count(key);
//访问键值 测试代码：
vector findSubstring(string s, vector& words) {vector result;
unordered_map c;
unordered_map n;
int j,i,k;
string ss;
int l = words[0].length();
for (string word : words)
c[word]++;
for(i=0;
i1;
i++)
{
j=i;
k=words.size();
n = c;
while(k)
{
ss = s.substr(j,l);
if(n[ss]<1)
{
break;
}
if(n.find(ss)!=n.end())
{
--n[ss];
j = j+l;
k--;
}else{
break;
}
}
if(k==0)
{
result.push_back(i);
}}
return result;
} 性能：
文章图片
参考答案：
class Solution {
public:
vector findSubstring(string s, vector& words) {
vector ret;
if(words.empty() || words[0].length()==0) return ret;
int wl=words[0].length();
int len=wl*words.size();
int end=s.length()-len;
if(end<0) return ret;
unordered_map dict;
for(string word : words) dict[word]++;
for(int st=0;
st& ret, unordered_map& dict, string& s, vector& words, int st, int end, int wl, int len) {
unordered_map hash;
int left=st, right=st;
while(left<=end) {
string nxt=s.substr(right, wl);
if(dict.count(nxt)==0) {
left=right+wl;
hash.clear();
}
else {
if(hash.count(nxt)==0) hash[nxt]=1;
else if(hash[nxt] 性能：
文章图片
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题