I found my wrong codes can pass the test


  • 0
    Y

    I wrote the following codes, it passed the test, but it was wrong.

    Like the following test case "abcd", ["a","abc","b","cd"]
    the function should return true, but it returned false.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            queue<string> q;
            
            q.push(s);
    
            int leftSize = s.size() + 1;
            
            while(!q.empty())
            {
                string cur = q.front();
                q.pop();
                        
                int wordSize = cur.size();
    
                if(wordSize < leftSize)
                {
                    leftSize = wordSize;
                    for(int i = 0; i < wordSize; i++)
                    {
                        string first = string(cur, 0, i + 1);
                        if(!dict.count(first))
                        {
                            continue;
                        }
                    
                        if(i == wordSize - 1)
                        {
                            return true;
                        }
                        //add left part into queue
                        q.push(string(cur, i+ 1));
                    }
                }
            }
            
            return false;
        }
    };

  • 0

    Thanks so much for your test case. I have added your test case to both Word Break and Word Break II, and your code should be judged as Wrong Answer now.


Log in to reply
 

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