Why my solution can not be accepted? I can not find the mistake!! Please help me!


  • 0
    W
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            if(s.size()==0)
                return false;
            set<int> prefix;
    
            static vector<bool> rec(s.size(),false);
            static vector<bool> flag(s.size(),false);
            for(unordered_set<string>::iterator it = dict.begin();it != dict.end();++it)
            {
                if(s[0] == (*it)[0])
                {
                    int j = 1;
                    int k = 1;
                    while(s[j] == (*it)[k] && j < s.size()&& k < (*it).size())
                    {
                        ++j;
                        ++k;
                    }
                    if(k == (*it).size())
                        prefix.insert(j);
                }
            }
            for(set<int>::iterator sit = prefix.begin();sit != prefix.end();++sit)
            {
                if(*sit == s.size())
                    return true;
                string temp = s.substr(*sit);
                int index = s.size()-(*sit)-1;
                if(!flag[index])
                {
                    rec[index] = wordBreak(temp,dict);
                    flag[index] = true;
                }
                if(rec[index])
                    return true;
            }
            return false;
        }
    };

  • 0
    W

    I modified my code as follows

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            if(s.size()==0)
                return false;
            vector<bool> rec(s.size(),false);
            vector<bool> flag(s.size(),false);
            
            return self_wordBreak(s,dict,rec,flag);
        }
        
        bool self_wordBreak(string s, unordered_set<string> &dict,vector<bool> &rec,vector<bool> &flag)
        {
            
            set<int> prefix;
            for(unordered_set<string>::iterator it = dict.begin();it != dict.end();++it)
            {
                string ts = s.substr(0,it->size());
                if(ts == *it)
                    prefix.insert(it->size());
            }
            for(set<int>::iterator sit = prefix.begin();sit != prefix.end();++sit)
            {
                if((*sit) == s.size())
                    return true;
                string temp(s.substr(*sit));
                int index = s.size()-(*sit)-1;
                if(!flag[index])
                {
                    rec[index] = self_wordBreak(temp,dict,rec,flag);
                    flag[index] = true;
                }
                if(rec[index])
                    return true;
            }
            return false;
        }
    };
    

    I think something wrong with the static variables, but I still don't know the reason, someone help?


  • 0
    W

    Ignore the difference in the fisrt for loop between two solution, it is not the key this question. they just do same work.


  • 0
    Q

    I once used static variables in the solution and got wrong answer strangely.

    Then I found that, the code is executed for different test cases, for each test case, the content in the variable "dict" may be different, so the content saved in the static variables may not meet the current case. Then it generates the wrong answer.

    To conclude, static variables are not recommended to use for this problem.


Log in to reply
 

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