TLE for Memoization in C++


  • 0
    V

    Please help me in identifying the bottleneck for this solution.

    class Solution {
    public:
        int removeBoxes(vector<int>& boxes) {
            if(boxes.size() <= 0) return 0;
            string strBoxes = convertBoxesToStr(boxes);
            unordered_map<string, int> cache;
            int maxPoints = 0;
            maxPoints = removeBoxesUtil(strBoxes, cache);
            return maxPoints;
        }
        
        string convertBoxesToStr(vector<int>& boxes) {
            string str = "";
            for(int i=0; i<boxes.size(); i++) {
                char c = boxes[i] + '0';
                str.push_back(c);
            }
            return str;
        }
        
        int removeBoxesUtil(string strBoxes, unordered_map<string, int> &cache) {
            if(strBoxes.length() <= 0) {
                return 0;
            }
            if(cache.find(strBoxes) != cache.end()) {
                return cache[strBoxes];
            }
            char c = strBoxes[0];
            int start = 0;
            int points = 0;
            int maxPoints = 0;
            string str = "";
            int index = 1;
            for(index=1; index<strBoxes.length(); index++) {
                if(strBoxes[index] == c) {
                    continue;
                }
                str = strBoxes.substr(0,start) + strBoxes.substr(index,strBoxes.length() - index);
                points = ((index-start) * (index-start)) + removeBoxesUtil(str, cache);
                maxPoints = max(maxPoints, points);
                start = index;
                c = strBoxes[index];
            }
            str = strBoxes.substr(0,start);
            points = ((index-start) * (index-start)) + removeBoxesUtil(str, cache);
            maxPoints = max(maxPoints, points);
            cache[strBoxes] = maxPoints;
            return maxPoints;
        }
    };
    

  • 0
    T

    substr calls in the loop of removeBoxesUtil are probably killing you. They create copies of the substring.


Log in to reply
 

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