首页 > 代码库 > 【LeetCode】Substring with Concatenation of All Words
【LeetCode】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).
记S长度为n，每个单词word长度为len，字典L共有size个单词。
逐位扫描，以[0,n-len*size]分别作为起始点，判断后续的len*size个word是否正好是字典L中的word。
有一点加速细节需要注意：
判断某个元素word是否在map中，可以判断m[word]是否为0（int 的默认值），这样可以节省时间。
class Solution {public: vector<int> findSubstring(string S, vector<string> &L) { vector<int> ret; if(S == "" || L.empty()) return ret; int n = S.size(); int len = L[0].size(); int size = L.size(); map<string, int> m; //count the L[i] string, and accelerate the find process for(int i = 0; i < size; i ++) {//if L[i] not exists, map will create a pair with default value <L[i], 0> m[L[i]] ++; } for(int i = 0; i <= n-len*size; i ++) {//at least len*size for all the words //start from i map<string, int> curM = m; int j; int count = 0; for(j = i; j < i+len*size; j += len) {//try size words start from i string word = S.substr(j, len); if(curM[word] != 0) //word exists in L //curM.find(word) != curM.end() curM[word] --; else //not found or found enough break; } if(j == i+len*size) //matched until end ret.push_back(i); } return ret; }};
【LeetCode】Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。