Why this solution cannot be accepted?


  • 0
    D

    My current solution is solution 1. The input of wrong answer is very long. If I change a little to solution 2, it can be accepted. I think the logic is same. Can anyone tell why? thank you!

    solution 1:

    bool wordBreak(string s, unordered_set<string> &dict) {
        int size = s.size();
        if(size ==0)
        {
            return true;
        }
        
        int dictSize = dict.size();
        if(dictSize == 0)
        {
            return false;
        }
        
        unordered_set<std::string>::const_iterator got;
        
        string str = s.substr(0, size);
        got = dict.find(str);
        
        if(got != dict.end())
        {
            return true;
        }
    
        vector<int> truePos;
        
        for(int i = 0; i< size; i++)
        {
            if(truePos.size() ==0)
            {
                string str = s.substr(0, i+1);
                got = dict.find(str);
                if(got != dict.end())
                {
                    truePos.push_back(i);
                }
            }
            else
            {
                //find the position of true;
                int j = truePos.size() -1;
                while(j>=0)
                {
                    string str = s.substr(truePos[j]+1, i-truePos[j]);
                    got = dict.find(str);
                    if(got != dict.end())
                    {
                        truePos.push_back(i);
                        break;
                    }
                    j--;
                }
            }
        }
        
        return truePos.size() == 0 ? false : truePos.back() == size-1;
    }
    

    solution2:

    bool wordBreak(string s, unordered_set<string> &dict) {
        int size = s.size();
        if(size ==0)
        {
            return true;
        }
        
        int dictSize = dict.size();
        if(dictSize == 0)
        {
            return false;
        }
        
        unordered_set<std::string>::const_iterator got;
        
        string str = s.substr(0, size);
        got = dict.find(str);
        
        if(got != dict.end())
        {
            return true;
        }
    
        vector<int> truePos;
        truePos.push_back(0);
        
        for(int i = 0; i< size; i++)
        {
            //find the position of true;
            int j = truePos.size() -1;
            while(j>=0)
            {
                string str = s.substr(truePos[j], i-truePos[j] + 1);
                got = dict.find(str);
                if(got != dict.end())
                {
                    truePos.push_back(i+1);
                    break;
                }
                j--;
            }
        }
        
        return truePos.back() == size;

Log in to reply
 

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