首页 > 代码库 > 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).
思路：直接使用DFS即可，使用map记录单词出现的情况。
1 class Solution { 2 public: 3 vector<int> findSubstring( string S, vector<string> &L ) { 4 vector<int> indices; 5 if( L.empty() ) { return indices; } 6 wordMap.clear(); 7 for( auto iter = L.begin(); iter != L.end(); ++iter ) { ++wordMap[*iter]; } 8 int slen = S.length(), wlen = L[0].length(), size = slen-wlen*(int)L.size(); 9 for( int i = 0; i <= size; ++i ) {10 if( SolveSub( i, S, wlen, (int)L.size() ) ) { indices.push_back( i ); }11 }12 return indices;13 }14 private:15 bool SolveSub( int start, string &S, const int wlen, int cnt ) {16 if( cnt == 0 ) { return true; }17 bool ret = false;18 auto iter = wordMap.find( S.substr(start, wlen) );19 if( iter != wordMap.end() && iter->second != 0 ) {20 --iter->second;21 ret = SolveSub( start+wlen, S, wlen, cnt-1 );22 ++iter->second;23 }24 return ret;25 }26 unordered_map<string,int> wordMap;27 };
Substring with Concatenation of All Words
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。