Share my c++ solution with only 5ms and easy to understand


  • 2
    Y
    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            int len=s.size();
            vector<bool >res(len,false);
            res.push_back(true);
            for(int i=len-1;i>=0;i--){
                for(int j=i+1;j<=len;j++){
                    if(res[j]){
                        if(dict.find(s.substr(i,j-i))!=dict.end()){
                            res[i]=true;
                            break;
                        }
                    }
                }
            }
            return res[0];
        }
    };

  • 0
    A

    Your solution is much more compact than one I read before. Compared with that one, yours takes less space. Moreover, I guess this one also needs less time. Thank you for your sharing.


  • 1

    In addition, we should calculate the effective length of the substring, here is my 0ms DP solution:

    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;
        }
    };

Log in to reply
 

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