[Word Break II] Why I cannot pass the test case "ab" ["a", "b"] and show the error: Runtime Error


  • 0
    Z
     vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> resultVector;
        if(s.size() == 0 )
            return resultVector;
        if(s.size() == 1)
        {
            unordered_set<string>::iterator itr = dict.find(s);
            if(itr != dict.end())
                resultVector.push_back(s);
            
            return resultVector;
        }
        
        int size = (int)s.size();
        bool** matrix = new bool*[size];
        for(int i = 0; i < size; i++)
            matrix[i] = new bool[size];
        
        for(int i = 0; i < size; i++)
            for(int j = 0; j < size; j++)
                matrix[i][j] = false;
    
        
        initWord(s,dict,matrix);
    
        
        string tempString;
        
        wordBreakCore(s, 0, dict, matrix, tempString, resultVector);
        
        for(int i = 0; i < size; i++)
            delete[] matrix[i];
        delete[] matrix;
        
        return resultVector;
    }
    
    void initWord(string s, unordered_set<string> &dict, bool** &matrix)
    {
        int size = (int)s.size();
        unordered_set<string>::iterator itr;
        
        for(int i = 0; i < size; i++)
        {
            for(int j = i; j < size; j++)
            {
                string temp = s.substr(i,j-i+1);
                itr = dict.find(temp);
                if(itr != dict.end())
                    matrix[i][j] = true;
                else
                    matrix[i][j] = false;
            }
        }
        return;
    }
    
    void wordBreakCore(string s, int index, unordered_set<string> &dict, bool** &matrix, string& tempString, vector<string>& resultString)
    {
        if(index == (int)s.size())
        {
            tempString.pop_back();
            resultString.push_back(tempString);
            return;
        }
        
        for(int i = index; i < (int)s.size(); i++)
        {
            if(matrix[index][i])
            {
                for(int k = index; k <=i; k++)
                    tempString.push_back(s[k]);
                tempString.push_back(' ');
                
                wordBreakCore(s, i + 1, dict, matrix, tempString, resultString);
                
                tempString.pop_back();
                for(int k = index; k<=i; k++)
                    tempString.pop_back();
            }
        }
        
    }
    

    matrix[i][j] is to judge whether it is a word from s[i] to s[j] .
    and wordBreakCore is use DFS to find the word.
    In my machine, It can pass the test ? Why When i submit it show the runTime Error?


Log in to reply
 

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