My slow but correct cpp code


  • 0
    C
    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words)
        {
            std::map<string, int> word_cnt;
            std::map<string, int>::iterator word_cnt_iter;
            for(string& word : words)
            {
                word_cnt_iter = word_cnt.find(word);
                if(word_cnt_iter == word_cnt.end())
                    word_cnt[word] = 1;
                else
                    word_cnt_iter->second++;
            }
            
            int word_len = words[0].size();
            int substr_len = word_len * words.size();
            
            vector<int> id_vec;
            
            for(int i=0; i <= (int)(s.size()) - substr_len; i++)
            {
                std::map<string, int> substr_cnt;
                bool flag = true;
                for(int j=i; j < i+substr_len; j += word_len)
                {
                    string tmp(s.begin()+j, s.begin()+j+word_len);
                    auto word_iter = word_cnt.find(tmp);
                    if(word_iter == word_cnt.end()) 
                    {
                        flag = false;
                        break;
                    }
                    int cnt = word_iter->second;
                    
                    word_iter = substr_cnt.find(tmp);
                    if(word_iter == substr_cnt.end())
                    {
                        substr_cnt[tmp] = 1;
                        continue;
                    }
                    
                    int cnt1 = word_iter->second;
                    if(cnt1 >= cnt) 
                    {
                        flag = false;
                        break;
                    }
                    word_iter->second++;
                }
                
                if(flag) id_vec.push_back(i);
            }
            
            return id_vec;
        }
    };

Log in to reply
 

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