4/05/2014

Leetcode -- Substring with Concatenation of All Words

Time Limit Exceeded:
 
class Solution {  
 public:  
  vector<int> findSubstring(string S, vector<string> &L) {  
     std::vector<int> result;  
     for(int i = 0; i < S.length(); ++i) {  
       if(isSubstring(S.substr(i), L)) {  
         result.emplace_back(i);  
       }  
     }  
     return result;  
   }  
   bool isSubstring(string s, const vector<string>& L) {  
     std::vector<string> tester(L);  
     while(!tester.empty()) {  
       bool found = false;  
       for(int i = 0; i < tester.size(); ++i) {  
         int l = tester[i].length();  
         if (s.substr(0, l) == tester[i]) {  
           tester.erase(tester.begin() + i);  
           found = true;  
           s = s.substr(l);  
           break;  
         }  
       }  
       if(!found) {  
         break;  
       }  
     }  
     return tester.empty();  
   }  
 };  

No comments: