0ms accepted c++ DP solution, calculate the effective length of the substring at first.


  • 0

    In order to avoid checks unnecessary substring, we should calculate the effective length of the substring at first.

    The follow is my accepted DP solution, and the return running time is 0ms.

    class Solution {
    public:
        bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {
    		if (dict.empty())
    			return false;
    		int len = s.size(), max_len = dict.begin()->size(), min_len = max_len;
    		for (auto it = dict.begin(); it != dict.end(); ++it)
    			if (it->size() > max_len)
    				max_len = it->size();
    			else if (it->size() < min_len)
    				min_len = it->size();
    		std::vector<int> flag(len + 1);
    		flag[len] = 1;
    		for (int i = len - 1; i >= 0; --i)
    			for (int j = min_len; j <= std::min(max_len, len - i); ++j)
    				if (flag[i + j] && dict.find(s.substr(i, j)) != dict.end()) {
    					flag[i] = 1;
    					break;
    				}
    		return flag[0] == 1;
        }
    };

  • 0
    F

    Hi! This is my short 0 ms C++ solution. Similar idea with you ( calculate the longest word length in the wordDict ). But I also make some other optimizations: 1. I define a bool variable 'is_brk' to check if we can break the 'for' loop earlier. 2. I define a vector 'ids' which only stores all the indexs that means s.substr(ids[j], ids[j+1]-ids[j]) is in the 'wordDict' while others don't. So in the inner 'for' loop, I only need to check the substring contained in 'ids'.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            int lens = s.size(), max_wordLen = 0;
            if(lens && wordDict.empty())   return false;
            for(auto &v : wordDict)
                if(v.size() > max_wordLen)
                    max_wordLen = v.size();
            vector<int> ids{0};
            bool is_brk;
            for(int i = 1; i <= lens; ++i) {
                is_brk = false;
                for(int j = ids.size()-1; j >= 0 && !is_brk && ids[j] >= i - max_wordLen; --j)
                    is_brk = wordDict.find(s.substr(ids[j], i-ids[j])) != wordDict.end();
                if(is_brk)
                    ids.push_back(i);
            }
            return (ids.back() == lens);
        }
    };

  • 0
    W
    This post is deleted!

  • 0
    W

    Hi , I just copy your code and find it didn't work , both in my own computer and OJ , and I think this line is weird : for (int i = len - 1; i >= 0; --i) you just traverse s from end to begin , and i think you should traverse from begin to end , if i were wrong , please tell me the where i am , thankyou very much!


  • 0

    The problem is max_len and min_len, update int len = s.size(), max_len = INT_MIN, min_len =INT_MAX; to int len = s.size(), max_len = dict.begin()->size(), min_len = max_len;, it will be OK. Thanks for your reminder.


Log in to reply
 

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