Do a full scan from the left to the right, O(n) C++, hashtable


  • 0
    H

    class Solution {
    public:
    vector<int> findSubstring(string s, vector<string>& words) {
    int nSizeWord = words[0].size();
    int nSizeW = words.size();
    int nS = s.size();
    vector<int> indices;
    unordered_map<string, int> hashW, hash2;
    int isN = 0;
    for(int i = 0; i< nSizeW; i++)
    {
    if(hashW[words[i]]) hashW[words[i]] += 1;
    else hashW[words[i]] = 1;
    }
    hash2 = hashW;
    int ip = 0;
    for(int i = 0; i < nS - nSizeWord*nSizeW + 1; i++)
    {

           for(int j = i; j < i + nSizeWord*nSizeW; j = j + nSizeWord )
           
          {  string sw = s.substr(j, nSizeWord);
           
            
            
            
            if(hash2[sw] > 0)
            { hash2[sw] -- ;
                isN++;
              }
             else
             {  
                isN = 0;
               hash2 = hashW; 
              break; 
             }
            
            if(isN == nSizeW) 
            { 
                indices.push_back(i);
              isN = 0;
              hash2 = hashW;
            
           }
          
             }
          
        
    }
    return indices;
    }
    

    };


Log in to reply
 

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