How to optimize my solution?

  • 1

    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 {
        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++){
            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) {
                        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.