Anyone who help check my codes to see why it said "Output Limit Exceeded"


  • 1
    A

    I searched here to see that it would occur if there was an infinite loop. Unfortunately, I checked time after time, but could not yet find out the cause. Please kindly help me, thanks.

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            map<string, vector<string> > str_vect;
            if (WordBreakPartial(0, s.size() - 1, s, dict, str_vect)) {
                return str_vect[s];
            } else {
                return vector<string>();
            }
        }
        
        bool WordBreakPartial(size_t from, size_t to, string& s, unordered_set<string>& dict, map<string, vector<string> >& str_vect) {
            if (str_vect.count(s.substr(from, to + 1 - from)) > 0) {
                return (str_vect[s.substr(from, to + 1 - from)].size() > 0) ? true:false;
            }
           
            str_vect[s.substr(from, to + 1 - from)] = vector<string>();
             
            if (from >= to) {
                // only one letter:
                if (dict.count(s.substr(from, 1)) > 0) {
                    str_vect[s.substr(from, 1)].push_back(s.substr(from, 1));
                    return true;
                }
                else {
                    return false;
                }
            }
     
            bool ret = false;
            for (size_t i = from; i < to; ++i) {
                if (((str_vect.count(s.substr(from, i + 1 - from)) == 0 && WordBreakPartial(from, i, s, dict, str_vect)) || str_vect[s.substr(from, i + 1 - from)].size() > 0) && 
                        ((str_vect.count(s.substr(i + 1, to - i)) == 0 && WordBreakPartial(i + 1, to, s, dict, str_vect)) || str_vect[s.substr(i + 1, to - i)].size() > 0)) {
    
                    vector<string>& left = str_vect[s.substr(from, i + 1 - from)];
                    vector<string>& right = str_vect[s.substr(i + 1, to - i)];
            
                    for (size_t j = 0; j < left.size(); ++j) {
                        for (size_t k = 0; k <right.size(); ++k) {
                            string tmp = left[j] + " " + right[k];
                            str_vect[s.substr(from, to + 1 - from)].push_back(tmp);
                        }
                    }
                    
                    ret = true;
                }
            }
            
            if (dict.count(s.substr(from, to + 1 - from)) > 0) {
                str_vect[s.substr(from, to + 1 - from)].push_back(s.substr(from, to + 1 - from));
                ret = true;
            }
            
            return ret;
        }
    };

  • 0
    W

    Please explain your approach conceptually and tell us the failure case.


  • 0
    A

    Hi. Thanks for your comments. Just unfortunately no failure case provided by leetcode, so even I myself have no idea of the bad case.

    The idea of my codings is to try to solve in a divide-and-conquer way (see func "WordBreakPartial"), while registering the done results (see "map<string, vector<string> > str_vect"; map a substr to a serial of possible results) for the future reference.


  • 0
    S

    @adrian2 Could you please just update your question post with your explanation? Thanks.


  • 2
    R

    The problem with your code is that it may count one answer more than once. You can try it with the given example "catsanddog". For one answer "cats and dog", your code (i.e. the long if statement) will break it into "cats" "anddog" and record the sentence after verifying each part. But later when trying "catsand" "dog" it will record the same sentence again.

    One possible fix is to skip the verification of the left part.

        for (size_t i = from; i < to; ++i) {
            string left = s.substr(from, i + 1 - from);
            if ((dict.count(left) > 0) && 
                    ((str_vect.count(s.substr(i + 1, to - i)) == 0 && WordBreakPartial(i + 1, to, s, dict, str_vect)) || str_vect[s.substr(i + 1, to - i)].size() > 0)) {
    
                vector<string>& right = str_vect[s.substr(i + 1, to - i)];
    
                for (size_t j = 0; j < right.size(); ++j) {
                    string tmp = left + " " + right[j];
                    str_vect[s.substr(from, to + 1 - from)].push_back(tmp);
                }
    
                ret = true;
            }
        }
    

Log in to reply
 

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