Using binary Search, since now we have a vector. Runtime: 6 ms


  • 0
    P

    Since we got a vector instead of a set, some people create a set out of the given vector. That is unnecessary since we are not going to add new elements to the set. We can simply sort the vector and do a binary search!

    Here's the code in C++

    class Solution {
    public:
    bool 
    wordBreak(string s, vector<string> &dict) {
            vector<bool> dp(s.size()+1,false);
            sort(dict.begin(), dict.end());
            
            dp[0] = true;
            for(int i = 1; i <= s.size(); ++i){
                for(int j = 0; j < i; ++j){
                    if(dp[j]){
                        if(dp[i]) break;
                        dp[i] = std :: binary_search(dict.begin(), dict.end(), s.substr(j, i - j));
                    }
                }
            }
            return dp[s.size()];
        }
    
    };

Log in to reply
 

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