Help! time limit exceeded.


  • 0
    Z

    My solution exceeds the time limit. Can anybody explain it? Thanks!

    class Solution {
    public:
    
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            unordered_map<int,vector<string>> res;
            vector<bool> bl(s.length(),false);
            for(int i=0;i<s.length();i++){
                for(int j=0;j<i;j++){
                    if(bl[j] && wordDict.find(s.substr(j+1,i-j))!=wordDict.end()){
                        bl[i]=true;
                        for(string& ins : res[j]){
                            string tmpstr=ins+" "+s.substr(j+1,i-j);
                            res[i].push_back(tmpstr);
                        }
                    }
                }
                if(wordDict.find(s.substr(0,i+1))!=wordDict.end()){
                    bl[i]=true;
                    res[i].push_back(s.substr(0,i+1));
                }
            }
            return res[s.length()-1];
        }
    };

  • 0
    S

    well, I just met the same problem and solved it successfully. May I can help you :)
    First, in your loop of j, you use

    for(int j=0;j<i;j++)
    

    Let n=s.length(), this loop will run n times. If s is very long, it may take a lot of time.
    Let m=maximum length of words in wordDict, then you just need to range j from i-m to i. The loop will be

    for(int j=max(0, j-m); j<i; j++)
    

    Second, your DP method will lead to an explosion in some special cases. For instance, suppose s is "aaaaa", and wordDict contains all strings which are formed with different numbers of "a", that is wordDict={"a", "aa", "aaa", "aaaa", ......}.
    According to your method, res[0]={"a"}, res[1]={"aa", "a a"}, res[2]={"aaa", "a aa", "aa a", "a a a"}. As you can see, the number of res[i] will increase exponentially. If s is very long, the time and space costs will be too large. If s="aaaaaaabaaaaaa", it can't be broken with given wordDict because there is one 'b' in it. However, in your DP method, you have to use exponential time to calculate res[i], at least before 'b'.
    When there are more 'a' before and after the 'b', you will get a TLE.
    So, my solution is to check whether the s can be broken by wordDict.

    May I can help you~


  • 0
    Z

    @shijx12 Thank you very much


  • 0
    C

    i met the same problem, how do u solve the second case in shijx12's reply ?


  • 0
    S

    @chenqun1218 I just check whether the s can be broken by wordDict at the beginning. If s can be broken, then the cost can't be avoid. If s can't be broken, you can return an empty vector directly.


Log in to reply
 

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