Easy to understand C++ Solution


  • 8
    X

    Using a vector to record if it is possible to have a combination of dictionary of words at point i.

    class Solution {
    public:
        bool wordBreak(string s, unordered_set<string>& wordDict) {
            s = "!" + s;
            vector<bool> dpArray(s.size());
            dpArray[0] = true;
            for(int i=0; i<s.size(); i++){
                for(int j=i+1; j<s.size(); j++) {
                    if(dpArray[j]) continue;
                    if(wordDict.find(s.substr(i+1, j-i))!=wordDict.end() && dpArray[i])
                        dpArray[j] = true;
                }
            }
            return dpArray[dpArray.size()-1];
        }
    };

  • 0
    C

    Can be accelerate by only searching substring no longer than longest string in dict.


  • 2

    Check from left to right is not a good idea, I think the best idea is to check from right to left. 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;
        }
    };

  • 0
    P

    Why left to right is not a good idea? Why right to left is better? Thanks!


  • 0

    I was wrong, they are all right. The key is calculate the effective length of the substring at first.


  • 0
    P

    If the size of dictionary is huge, the calculations in dictionary would be a cost. If the string size is huge, the calculation would benefit. In fact, min_len can be assumed as 1, max_len may be 20. We can get the accurate answer from a real dictionary. :)


Log in to reply
 

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