Time Limit Exceeded. A very normal algorithm...


  • 0
    Z
    class Solution {
    public:
        vector<int> findSubstring(string S, vector<string> &L) {
            //There may be duplicate words in L
            int Ssize = S.size();
            int m = L.size();
            int k = L[0].size();
            unordered_map<string, int> word;
            vector<int> res;
            for(int i = 0; i < m; ++i)
                word[L[i]]++;
            for(int i = 0; i <= Ssize - k * m; ++i) {//if I use i <= S.size() - k * m directly, it is wrong because S.size() is                                      //                                               the type of size_t
                if(word.find(S.substr(i, k)) == word.end())
                    continue;
                else {
                    unordered_map<string, int> hm = word;
                    int j = i;
                    while(true) {
                        if(hm.find(S.substr(j, k)) == hm.end())
                            break;
                        else {
                            if(hm[S.substr(j, k)] == 1)
                                hm.erase(S.substr(j, k));
                            else
                                hm[S.substr(j, k)]--;
                            j += k;
                            if(hm.size() == 0) {
                                res.push_back(i);
                                break;
                            }
                        }
                    }
                }
            }
            return res;
        }
    };
    

    Time Limit exceeded when meet a very long test case.

    My algorithm is naive. use a map to store the string and it's number. and minus one when meet a string in S. if reduce to one, then remove this item from the map.


  • 5
    S

    Your algorithm is brute force time complexity is O((M - N) * N), letting M be length of S and N be length of L array. So it won't pass all test case. The best solution is O(M * Len), where Len is the length of string in L.

    Have you ever solved this Minimum Window Substring ? It may help you to come up a better solution.

    To solve Minimum Window Substring, you can read this article.


  • 0
    Z

    I don't think it's because my algorithm because others who use the same algorithm has been accepted(like http://n00tc0d3r.blogspot.com/search?q=Permutations#!/2013/06/substring-with-concatenation-of-all.html).


  • 0
    S

    I get your problem. You over used S.substr(j, k), it will cost time everytime. You should save it to a temp variable, then use this variable instead of S.substr(j, k).


  • 0
    Z

    Yes! It has been accepted! I will focus on such details later! Thank you sooooooo much!!


  • 0
    Z

    But I don't think make such a change will reduce the time complexity in big O notation, right?
    In addition, if substr(begin, len) is O(len), the total time is (S.size() - L.size()*L[0].size()) * L.size()*L[0].size(), right?


  • 0
    H

    Minimum Window Substring is right


  • 0
    Q

    “ if(word.find(S.substr(i, k)) == word.end())
    continue; ”
    This sentence is the key, it can avoid the unnecessary copy of the map


Log in to reply
 

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