赞
踩
- /*本题和Minimum Window Substring题目很相似:都利用双指针在第一个数组中标志一个区间,
- 让这个区间满足第二个数组表示的某种属性,目的是在第一个数组中寻找出满足这种属性的区间。
- 源代码参考自:http://www.cnblogs.com/panda_lin/archive/2013/10/30/substring_with_concatenation_of_all_words.html*/
- class Solution {
- public:
- vector<int> findSubstring(string S, vector<string> &L) {
- std::vector<int> result;
-
- if(L.empty() || S.empty()) return result;
-
- int word_len(L[0].size()), letter_num(L.size()*L[0].size());
- if(S.size() < letter_num) return result;
-
- std::map<string, int> expected_count;
- for(int i = 0; i < L.size(); ++i){
- ++expected_count[L[i]];
- }
- std::map<string, int> appeared_count;
- for(int i = 0; i <= S.size() - letter_num; ++i){
- appeared_count.clear();
- int j;
- for(j = 0; j < L.size(); ++j){
- std::string word = S.substr(i + j*word_len, word_len);
- if(expected_count.find(word) != expected_count.end()){
- ++appeared_count[word];
- if(appeared_count[word] > expected_count[word]) break;
- }
- else{
- break;
- }
- }
- if(j == L.size()) result.push_back(i);
- }
-
- return result;
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。