首页 > 代码库 > Substring with Concatenation of All Words
Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
思路：这道题意思是说满足全部包含L中单词且中间无其他干扰项，返回这样的条件的开头和结尾索引。这道题主要使用map数据结构来解题，主要是使用map来记录L中单词出现的次数。循环遍历字符串，找出存在与L中的字符串且L中单词必须连续、全部出现。查找某个单词成功后将这个单词加入到新的map容器中，这个容器存储的是从当前指针位置开始满足单词列表的单词，同时统计次数，接下来如果这个但是在新容器出现的次数是否小于等初始化容器的次数。如果大于，则是错误的，指针后移。然后在找出其他L中的单词。(注意L中单词必须连续出现)最后我们后移单词列表中指定个数的单词或者因为不匹配而终止从指针位置i开始，如果查找成功就把当前指针的位置记录下来。如此找出所有满足条件的情况。
class Solution {public: vector<int> findSubstring(string S, vector<string> &L) { int wordNum=L.size(); int wordLen=L[0].size(); int sLen=S.size(); vector<int> result; result.clear(); if(sLen<=0 || wordNum<=0) return result; map<string,int> words,curs; for(int i=0;i<wordNum;i++) { words[L[i]]++; } for(int i=0;i<=(sLen-wordNum*wordLen);i++) { curs.clear(); int j=0; for(;j<wordNum;j++) { string word=S.substr(i+j*wordLen,wordLen); if(words.find(word)==words.end()) break; curs[word]++; if(words[word]<curs[word]) break; } if(j==wordNum) { result.push_back(i); } } return result; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。