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

  • 0

    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 {
    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[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.