How to optimize my solution?


  • 1
    C

    I use vector<bool> track to indicate whether the substring of s which has length i is valid. If track[j] and s.substr(j, i-j) is valid, then append s.substr(j, i-j). But my solution consumes too much memory. So do you know how to optimize it?

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string> &dict) {
            vector<bool> track(s.length()+1, false);
            track[0] = true;
            
            vector<vector<string> > record;
            for(int i=0; i<=s.length(); i++){
                record.push_back(vector<string>());
            }
            
            for(int i=1; i <= s.length(); i++){
                for(int j=i-1; j>=0; j--){
                    if(track[j] && dict.count( s.substr(j, i-j) ) ){
                        track[i] = true;
                        string t = s.substr(j, i-j);
                        if(record[j].size()==0) {
                            record[i].push_back(t);
                            continue;
                        }
                        for(int k=0; k < record[j].size(); k++){
                            string tmp = record[j][k];
                            record[i].push_back(tmp+" "+t);
                        }
                    }
                }
            }
            return record[s.length()];
        }
    };

Log in to reply
 

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