Does the order of the possible solution matter?


  • 0
    C

    I think my code gets a wrong answer as a result of order problem, and here is my recursive code.

    void myWordBreak(string &s, int st, unordered_set<string> &dict, vector <int> &lenOpt, int &lensize, vector<string> &ret, string &sen) {
    if (st == s.size()) {
    	ret.push_back(sen);
    	return;
    }
    for (int i = 0; i < lensize; ++i) {
    	if (st+lenOpt[i] > s.size()) break;
    	string word = s.substr(st, lenOpt[i]);
    	if (dict.find(word) != dict.end()) {
    		if (sen.empty()) {
    			sen.append(word);
    			myWordBreak(s, st+lenOpt[i], dict, lenOpt, lensize, ret, sen);
    			sen.erase(st, lenOpt[i]);
    		} else {
    			sen.append(1, ' ');
    			sen.append(word);
    			myWordBreak(s, st+lenOpt[i], dict, lenOpt, lensize, ret, sen);
    			sen.erase(st, lenOpt[i]+1);
    		}
    	}
    }
    }
    
    int getId(char ch) {
    return (int)ch;
    }
    
    vector <string> wordBreak(string s, unordered_set<string> &dict) {
    vector <string> ret;
    if (s.empty() || dict.empty()) return ret;
    
    int letters[256];
    for (int i = 0; i < 256; ++i) {
    	letters[i] = 0;
    }
    vector <int> lenOpt;
    
    unordered_set<string>::iterator itr;
    for (itr = dict.begin(); itr != dict.end(); ++itr) {
    	lenOpt.push_back((*itr).size());
    	for (int i = 0; i < (*itr).length(); ++i) {
    		++letters[getId((*itr)[i])];
    	}
    }
    
    for (int i = 0; i < s.length(); ++i) {
    	if (letters[getId(s[i])] == 0) {
    		return ret;
    	}
    }
    
    sort(lenOpt.begin(), lenOpt.end());
    int ind = 1;
    for (int i = 1; i < lenOpt.size(); ++i) {
    	if (lenOpt[i] != lenOpt[i-1]) {
    		lenOpt[ind++] = lenOpt[i];
    	}
    }
    string sentence = "";
    myWordBreak(s, 0, dict, lenOpt, ind, ret, sentence);
    
    return ret;
    }

  • 0
    M
    This post is deleted!

  • 0
    M

    In this problem, no, the order of the solutions doesn't matter. Because of this, it can sometimes be difficult to see if you have all the solutions, if you duplicated one, or if you changed one from the correct value. Would you mind showing us the input, expected output, and your output for the test case you are failing? It may help with deciphering the problem.


  • 0
    C

    I sorted the solutions, and found out that it was a result of duplicated ones, thank you for your advice!


Log in to reply
 

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