Word Break, can't find where the problem is. It runs well on Qt.


  • 0
    T
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            string scopy = s;
            for(int i = 0 ; i < s.size(); i++){
                for(string word: dict){
                    if(scopy.substr(0, word.size()) == word) {
                        string::size_type num = word.size();
                        scopy.erase(0, num);
                        continue;
                    }
                }
                if(scopy.size()==0) break;
            }
            return (!scopy.size());
            
        }
    };
    

    The feedback from leetcode was:

    Input: "abcd", ["a","abc","b","cd"]

    Output: false

    Expected: true.

    I copied the same program on Qt, and checked the size of output. It ran well on my PC. Just can't find wat is wrong. Thanks to anyone who is willing to give a helping hand.


  • 1
    H

    unordered_set doesn't have order, that mean the order of the words in the set is randomly.
    When u ran your code on your computer.
    The order of words maybe ["a","abc","b","cd"].
    So your result of "abcd" was true. It deleted "a" "b" "cd" one by one.
    However, the order of words can be ["abc","a","b","cd"].
    In this case, the result of your code is false, because it deletes "abc" first, and scopy remains "d", which is not in dict.


  • 0
    T

    Thank you. As far as I understand, In fact, we need to check every possibility. Under this instruction, when we find "abc" is not the right prefix, we can drop it and go on to another prefix match "a", to see whether it works with "a" as the first letter. Is that right?


  • 0
    H

    Yes, exactly. Nevertheless, with DP or GA, you can achieve it in time complexity O(n^2).


Log in to reply
 

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