当前位置:   article > 正文

LeetCode之Substring with Concatenation of All Words

substring with concatenation of all words
  1. /*本题和Minimum Window Substring题目很相似:都利用双指针在第一个数组中标志一个区间,
  2. 让这个区间满足第二个数组表示的某种属性,目的是在第一个数组中寻找出满足这种属性的区间。
  3. 源代码参考自:http://www.cnblogs.com/panda_lin/archive/2013/10/30/substring_with_concatenation_of_all_words.html*/
  4. class Solution {
  5. public:
  6. vector<int> findSubstring(string S, vector<string> &L) {
  7. std::vector<int> result;
  8. if(L.empty() || S.empty()) return result;
  9. int word_len(L[0].size()), letter_num(L.size()*L[0].size());
  10. if(S.size() < letter_num) return result;
  11. std::map<string, int> expected_count;
  12. for(int i = 0; i < L.size(); ++i){
  13. ++expected_count[L[i]];
  14. }
  15. std::map<string, int> appeared_count;
  16. for(int i = 0; i <= S.size() - letter_num; ++i){
  17. appeared_count.clear();
  18. int j;
  19. for(j = 0; j < L.size(); ++j){
  20. std::string word = S.substr(i + j*word_len, word_len);
  21. if(expected_count.find(word) != expected_count.end()){
  22. ++appeared_count[word];
  23. if(appeared_count[word] > expected_count[word]) break;
  24. }
  25. else{
  26. break;
  27. }
  28. }
  29. if(j == L.size()) result.push_back(i);
  30. }
  31. return result;
  32. }
  33. };

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号