What's my code's time complexity?


  • 1
    A
    class Solution {
    private:
    	std::vector<int> isTrue;
    	std::vector<std::vector<std::string>> midResult;
    
    	void contactWords(const std::string& word, std::vector<std::string>& words){
    		int len = words.size();
    		for(int i = 0; i < len; ++i){
    			words[i] = word + " " + words[i];
    		}
    	}
    
    	void pushWords(std::vector<std::string>& words, const std::vector<std::string>& temp){
    		int len = temp.size();
    		for(int i = 0; i < len; ++i){
    			words.push_back(temp[i]);
    		}
    	}
    public:
    	std::vector<std::string> wordBreak(std::string s, std::unordered_set<std::string> &dict) {
    		std::vector<std::string> result;
    		int len = s.size();
    		isTrue.clear();
    		midResult.clear();
    		isTrue.resize(len, 0);
    		midResult.resize(len, std::vector<std::string>());
    		std::string word = "";
    		for(int i = 0; i < len; ++i){
    			word += s[i];
    			if(dict.find(word) != dict.end()){//If find the current word
    				if(i != len - 1){ //Not the end of sentence s
    					if(isTrue[len - i - 2] == 0){//The first time
    						midResult[len - i - 2] = wordBreak(s.substr(i + 1, len - i), dict);
    						if(midResult[len - i - 2].size() != 0){//Find a solution
    							isTrue[len - i - 2] = 1;
    						}else{
    							isTrue[len - i - 2] = -1;
    						}
    					}
    					if(isTrue[len - i - 2] == 1){//Find a solution
    						std::vector<std::string> temp = midResult[len - i - 2];
    						contactWords(word, temp);
    						pushWords(result, temp);
    					}
    				}else{//Reached the end of the sentence s, so just push_back and return
    					result.push_back(word);
    					return result;
    				}
    			}
    		}
    		return result; //Return all the solutions
        }
    };
    
    1. vector<int> isTrue is used to indicate if one specific sub-problem has already been computed or not
    2. vector<vector<string>> midResult is used to store the result of each sub-problem
    3. void contactWords(string, vector<string>) is used to get a final result for some specific solutions
    4. void pushWords(vector<string>, vector<string>) is used to store the final result

Log in to reply
 

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