Who can show me a DP solution. Thanks.


  • 2
    M

    This is my solution. But the time complexity isn't good.

    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || dict == null) return false;
        Iterator<String> iterator = dict.iterator();
        while (iterator.hasNext()) {
            s = cutStr(s, iterator.next());
            if (s.isEmpty()) {
                return true;
            }
        }
        return false;
    }
    
    private String cutStr(String orgStr, String subStr) {
        int index = orgStr.indexOf(subStr);
        if (index != -1) {
            char[] res = new char[orgStr.length() - subStr.length()];
            for (int i = 0, j = 0; i < orgStr.length(); i++) {
                if (i < index || i > (index + subStr.length() - 1)) {
                    res[j++] = orgStr.charAt(i);
                }
            }
            return new String(res);
        }
        return orgStr;
    }

  • 0

    Did you read the FAQ? Questions asking for code/solution must demonstrate a minimal understanding for the problem being solved. Include attempted solutions, why they didn't work, and the expected results.

    Trust me, you will learn much better that way rather than expecting others to provide solution to you -- which you will learn almost nothing.


  • 2
    S

    Here is mine. I use 2 dictionaries to keep good and bad words.

    class Solution {
    public:
        bool wordBreakDP(string s, unordered_set<string > &dpDict, unordered_set<string > &badDict){
            if (badDict.find(s) != badDict.end()){
                return false;
            }else if (dpDict.find(s) != dpDict.end()){
                return true;
            }else if (s.size() < 2){
                return false;        
            }else{
                for (int i = 1; i < s.size(); ++i){
                    string sub1 = s.substr(0, i);
                    string sub2 = s.substr(i);
                    if (wordBreakDP(sub1, dpDict, badDict)){
                        dpDict.insert(sub1);
                    }else{
                        badDict.insert(sub1);
                    }
                    if (wordBreakDP(sub2, dpDict, badDict)){
                        dpDict.insert(sub2);
                    }else{
                        badDict.insert(sub2);
                    }
                    if (wordBreakDP(sub1, dpDict, badDict) and wordBreakDP(sub2, dpDict, badDict)){
                        dpDict.insert(s);
                        return true;
                    }
                }
            }
            badDict.insert(s);
            return false;
        }
        bool wordBreak(string s, unordered_set<string> &dict) {
            unordered_set<string > dpDict(dict);
            unordered_set<string > badDict;
            return wordBreakDP(s, dpDict, badDict);
        }
    };
    

  • 36
    S

    Bottom up DP

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

    edit:
    dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.

    For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous iteration in outer loop.


  • 0
    S

    Thanks for your sharing. Could you please update your answer to detail your solution, like what's the meaning of dp[], and how to calculate it? Idea is better than code.


  • 0
    C

    Your solution is wrong.

    Bad Case 1:

    s = "bac", dict = ["bc", "a"]

    Suppose the iterator first takes "a" from the dict, then you get a return value "bc" from the cutStr method, then s = "bc" and iterator.next() is "bc" now, so you get a true value finally, which is wrong.

    Bad Case 2:

    s = "abab", dict = ["ab"]

    The answer should be obviously true.
    Your iterator takes "ab" from the dict first, and the return string is "ab", which still need to be processed, but there is no element in the iteration, so you get a false value.


  • 0
    G

    I use a map M to store the substrings that have already been checked for their presence in the dicitonary and the result i.e. 0 or 1 indicating that they were absent or present respectively.

    class Solution {
    public:
    map<string,int> M;
    bool wordBreak(string s, unordered_set<string> &dict) {
    
        if(M.find(s)!=M.end())
           return M[s] ? true : false;
    
        int i,j;
        string t="",t1;
        for(i=0;i<s.size();i++)
        {
            t += s[i];
            if(dict.find(t)!=dict.end())
                {
                    M[t]=1;
                    j=i+1;
                    t1 = s.substr(j,s.size()-j);
                    if(t1.size() ==0 || wordBreak(t1,dict))
                        return true;
                }
            else
                M[t]=0;
    
        }
        return false;
    }
    };

  • 0
    N
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 3
    N

    My DP solution. DPB[i]=true means substring s.substr(0,i) is breakable. so the solution is to find DPB[len].

    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        if(len==0) return true;
        if((len == 1) &&(dict.find(s)!=dict.end())) 
            return true;
        else if(len == 1)
            return false;
    
        int *DPB = new int[len+1];       //DPB[i]=true: substr (start from 0, length=i) breakable, find DPB[len]
        for(int i=0; i<=len; i++)
            DPB[i] = false;
        DPB[0] = true;
        DPB[1] = (dict.find(s.substr(0,1)) != dict.end());
    
        for(int i=1; i<s.length(); i++)
        {
            for(int j=i; j>=0; j--)
            {
                string sub = s.substr(j, i-j+1);
                if((dict.find(sub)!=dict.end()) && DPB[j])
                {
                    DPB[i+1]=true;
                    break;
                }
            }
        }
        bool res = DPB[len];
        delete []DPB;
        return res;
    }

  • 22
    H
    public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        int length = s.length();
        boolean[] can = new boolean[length+1];
        can[0] = true;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if (can[j] && dict.contains(s.substring(j, i))) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[length];
    }
    

    }


  • 0
    S

    Hi @henryyao, Thanks again for your another post. Same advice, format your code correctly and try to add words explain your idea or code. Thanks.


  • 0
    A
    class Solution {
    private:
    	std::vector<int> isTrue;
    public:
            bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {
    		int len = s.size();
    		isTrue.clear();
    		isTrue.resize(len, 0);
    		std::string word = "";
    		for(int i = 0; i < len; ++i){
    			word += s[i];
    			if(dict.find(word) != dict.end()){//If find the current word
    				if(i != len - 1){
    					if(isTrue[len - i - 2] == 0){
    						if(wordBreak(s.substr(i + 1, len - i), dict)){
    							isTrue[len - i - 2] = 1;
    						}else{
    							isTrue[len - i - 2] = -1;
    						}
    					}
    					if(isTrue[len - i - 2] == 1){
    						return true;
    					}
    				}else{
    					return true;
    				}
    			}
    		}
    		return false;
        }
    };
    

    This is my own solution, it's run time is 32ms. My analysis is as follows:

    1. At the very beginning, I thought recursive will be fine. It's for sure that there is a TLE problem
    2. Then I analysed the problem and found that there are just n - 1 sub-problems in the recursive version. So why do not I save the result of each sub-problem at the first time I encounter it and use the saved result next time we encounter it.
      Thanks.

  • 0
    A

    vector isTrue is used to save the result of all the sub-problems so we just need to compute each sub-problem once.


  • 0
    J

    an error in your code. In the inside for loop, you define j = i, then the substring should be s.substr(i, j+1).


  • 0
    S

    He was right. the second parameter in s.substr() is the length. Hence if you want substring between i and j it is always substr(i, j-i+1)


  • 0
    S

    I had the same thought but I used an helper function and a top-down DP.

    your code is elegant as FUCK! Respect!


  • 0
    B

    @joybing At first glance, I had same idea as you. Then, I realized that this is a C++ solution. The second argument of substr() in C++ is different from substring() in Java.


  • 0
    F

    Top down memoization (not real DP)

    class Solution:
    # @param s, a string
    # @param dict, a set of string
    # @return a boolean
    def wordBreak(self, s, dict):
        cache = {"":True}
        def parser(remain):
            if remain in cache:
                return cache[remain]
            for i in range(len(remain)):
                if (remain[:i+1] in dict) and parser(remain[i+1:]):
                    cache[remain]=True
                    return True
            cache[remain]=False
            return False
        return parser(s)
    

    just remember all sub-strings that parser have seen to avoid re-evaluation.
    DP solves problems in a bottom up manner;
    memoization do things top-down


  • 4
    F

    Here is a top down DP solution :

    Points worth noting:

    1. Any breakable string must also be breakable if we divide it into two substrings properly.
      There are only N - 1 ways of dividing a string into two parts, with N the length of the string.
      So our task is to find a proper way out of these N - 1 ones. (only one will do since the problem does not
      ask us to find all ways.)

    2. To avoid repetition, we use a HashMap to store the results for each substring, which are obtained in turn by calling wordBreak() method.

    3. The total string is breakable if its two complementary substrings are breakable. Once we get the results for both parts, we can check this by getting the results from the HashMap.

    In total the program will run in O(n^2) time with n the length of the string. Here is the program:

        public class WordBreak {   
        	private Map<String, Boolean> myMap = new HashMap<>();
        	
        	public boolean wordBreak(String s, Set<String> dict) {
        		// check if the dictionary contains the whole string		
        		if (dict.contains(s)) {
        			return true;
        		}
        
        		// divide the string and check for each substring
        		for (int i = 1; i < s.length(); i++) {			        			
        			// check for the left half substring
        			if (!myMap.containsKey(s.substring(0,i))) {			
        				myMap.put(s.substring(0,i), wordBreak(s.substring(0,i), dict));				
        			}
        			
        			// check for the right half substring
        			if (!myMap.containsKey(s.substring(i, s.length()))) {			
        				myMap.put(s.substring(i, s.length()), wordBreak(s.substring(i, s.length()), dict));				
        			}
        			
        			// if both substrings are breakable, then the total string is also breakable
        			if (myMap.get(s.substring(0,i)) && myMap.get(s.substring(i, s.length()))) {
        				return true;
        			}
        		}	
        		
        		// else the string is not breakable
        		return false;						
        	}
        }

Log in to reply
 

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