本文共 1252 字，大约阅读时间需要 4 分钟。

30.串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

暴力法

• 将words数组中的字符串都存入一个哈希表中，从双指针遍历s字符串，一个指针位于遍历头部，另一个以words数组中单个字符串长度为步长从i位置遍历，如果j遍历到的字符串在哈希表中没有，直接i++，若有，存入一个辅助的哈希表接着遍历，直到长度达到结果长度。如果辅助哈希表与原哈希表完全一样，则将i存入结果数组，最后清空辅助哈希表，继续遍历。

class Solution {public:    vector
   
     findSubstring(string s, vector
    
     & words) {        if(s.empty() || words.empty()) return {};                unordered_map
     
       m1,m2;        vector
      
        res;        int wordlength=words[0].size();        int resultlength=words.size()*wordlength;        if(s.size() < resultlength) return {};        for(int i=0;i < words.size();i++){            m1[words[i]]++;        }        for(int i=0;i <= s.size()-resultlength;i++){            int j=i;            while(j < s.size() && j < i+resultlength){                if(m1.find(s.substr(j,wordlength)) == m1.end()){                    break;                }                else{                    m2[s.substr(j,wordlength)]++;                }                j += wordlength;            }            if(j-i == resultlength && m2 == m1) res.push_back(i);            m2.clear();        }        return res;    }};
      
     
    
   

通过时间：

转载地址：http://tiemb.baihongyu.com/