Got wrong answer when Input: "ab", ["a","b"]


  • 0
    R

    Hi,

    I am trying to complete the test Word Break II .

    I got the wrong answer message shows below:

    Input: "ab", ["a","b"]
    Output: []
    Expected: ["a b"]

    However, when I ran the test in my machine and it got correct answer.
    Is there any reason that cause this issue?

    Thanks

    Below is my code:

    =======================================================

    void sub_wordBreak(string s, unordered_set<string> &dict, vector<string>& solutions, bool** A, int j, string& result){ //j = start
    
            for(int k = 1; k <= s.size() - j; k++){ //size of first part
                    if((dict.find(s.substr(j,k)) != dict.end()) ) {
                        if(k == s.size()-j){
                            result.append(s.substr(j,k));
                            solutions.push_back(result);
                            result.resize(result.size() - k);
                        }
                        else if(A[j+k][s.size()-(k+j)]){
                            result.append(s.substr(j,k)).append(" ");
                            sub_wordBreak(s, dict, solutions, A, j+k, result);
                            result.resize(result.size() - k - 1);
                        }
                    }
            }
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
         vector<string> solutions;
         if(s.size() == 0) return solutions;
    
         int length = s.size();
         bool** A = new bool*[length];
         for(int i = 0; i < length; i++){
                 A[i] = new bool[length];
         }
         //A[start][size-1]
         //initialize 
         for(int j = 0; j < s.size(); j++){ //start
                         if(dict.find(s.substr(j,1)) != dict.end()){ //find
                                A[j][0] = true;
                         }
                         else A[j][0] = false;
         }
         for(int i = 1; i <= s.size(); i++){ //size
                 for(int j = 0; j <= s.size() - i; j++){//start
                         if(dict.find(s.substr(j,i)) != dict.end()){
                                 A[j][i-1] = true;
                         }
                         else{
                              for(int k = 1; k < i; k++){//size of first part
                                 if(A[j][k-1]&A[j+k][i-k-1]) {
                                     A[j][i-1] = true;
                                     break;
                                 }
                                 else A[j][i-1] = false;
                              }
                         }
                 }
         }
    
         if(A[0][s.size()-1] == 0) return solutions;
         string result;
         sub_wordBreak(s, dict, solutions, A, 0, result);
         return solutions;
    }

Log in to reply
 

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