Solution worked in my vs, but i got a wrong answer


  • 1
    T

    the case is:

    Input:	"aaaaaaa", ["aaaa","aaa"]
    Output:	false
    Expected:	true
    

    and my solution is:

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            size_t pos = 0;
            for (auto i = dict.begin(); i != dict.end(); ++i) {
                if ((pos = s.find(*i)) != string::npos) {
                    findallandremove(s, *i);
                    if (s.empty())
                        return true;
                }
            }
            
            return false;
        }
        
    private:
        void findallandremove(string &src, string str2find) {
            size_t pos = 0;
            while ((pos = src.find(str2find, pos)) != string::npos) {
                src.replace(pos, str2find.length(), "");
            }
        }
    };
    

    could any one help me?


  • 1
    P

    This greedy approach doesn't seem to work


  • 0
    A

    your greedy approach is incorrect

    for example:
    Input: "atest", ["a", "at", "test"]
    the order of words in dict is not predictable,
    according to your approach, if the first word in dict is "at", "at" will be removed from s, the rest part "est" can't be broken.
    Actually, "atest" can be broken into "a" ,"test"


Log in to reply
 

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