hashmap


  • 0
    B
    class Solution {
    public://author:qiuqian,freebug,,思路:用一个hashmap存住words中出现的词的所有次数,然后按照words.size()*words[0]的长度,依次选取s的字串,
        //然后在该字串中按照words[0]的长度在选字串,在hashmap中进行匹配,匹配上就减1,最后判断hashmap中的所有字串数目都为0,为0就把该索引放入结果
        //否则重新循环。time:o(n^2)
        vector<int> findSubstring(string s, vector<string>& words) {
            int vec_len = words.size();
            int word_len = words[0].size();
            int len = vec_len * word_len;
            vector<int> res;
            for(int i = 0;i < s.size()-len+1;i++){
                unordered_map<string,int> m;
                for(auto word:words) m[word]++;
                string tmp = s.substr(i,len);
                for(int j = 0;j < len;j += word_len){
                    string cur = tmp.substr(j,word_len);
                    if(m.find(cur) != m.end() && m[cur] > 0){
                        m[cur]--;
                    }else break;
                }
                auto it = m.begin();
                for(;it != m.end();it++){
                    if(it->second != 0) break;
                }
                if(it == m.end()) res.push_back(i);
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.