首页 > 代码库 > Substring with Concatenation of All Words
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"]
You should return the indices: [0,9].
(order does not matter).
class Solution {public: vector<int> findSubstring(string s, vector<string> & words) { int nums = words.size(), n = s.length(), len = words[0].length(); vector<int> ret; unordered_map<string, int> count; for (string word : words) count[word]++; for (int i = 0; i < n - len * nums + 1; i++) { unordered_map<string, int> seen; int j = 0; for (; j < nums; j++) { string str = s.substr(i + j * len, len); if (count.find(str) != count.end()) { seen[str]++; if (seen[str] > count[str]) break; }else{ break; } } if(j == nums) ret.push_back(i); } return ret; }};
Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。