[HELP] really have no idea why my DP solution get a TLE. This should have a same result as accpected recursion solution(memorized)


  • 0
    F

    The idea is to use a DP array vector<vector<string>> to remember word break result at each idx. Traverse from the head of the string to the end. And for each idx, iterate all possible word and add to previous idx result. As the code show:

    class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<vector<string>> dp(s.size(), vector<string>(0));
            int max_s = 0;
            for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); it++) {
                max_s = max(max_s, (int)(*it).size());
            }
            
            for (int i = 0; i < s.size(); i++) {
                for (int j = i; j >= 0 && i - j + 1 <= max_s; j--) {
                    string cur_string = s.substr(j, i - j + 1);
                    
                    if (wordDict.find(cur_string) != wordDict.end()) {
                        // found a string from idx j to i.   
                        // Add the cur_string to each string in result we already
                        // got from dp[j-1]
                        if (j == 0) {
                            dp[i].push_back(cur_string);
                        } else if (dp[j-1].size() > 0){
                            for (int k = 0;  k < dp[j-1].size(); k++) {
                                dp[i].push_back(dp[j-1][k] + " " + cur_string);
                            }
                        }
                    }
                }
            }
            
            return dp.back();
        }
    };
    

    Per my understanding, this solution didn't do any redundant work comaparing to recursion. However, this code get TLE consistently. Can anyone take a look and see if I missed anything here?

    Thanks!!


  • 0
    S

    I guess it might be due to two reasons:

    • You looped from 1 to the length of the longest word in wordDict. If there is at least one single very very long word in wordDict, and if there are not many words in wordDict, then your algo does lots of unnecessary checks.
    • The recursive method fills only the queried parts of the DP table. However, an iterative method usually fills the entire table even if some parts of it is not needed. Example input: s = "aaaaaaaa", dict = ["aaaa"].

    The following is my Java approach which fixes the two issues above

    public class Solution {
        private ArrayList<LinkedList<String>> dp;
        private String s;
        private Set<String> wordDict;
        private Set<Integer> wordSizes;
        public List<String> wordBreak(String s, Set<String> wordDict) {
            dp = new ArrayList<LinkedList<String>>(s.length()+1);
            for(int i=0;i<=s.length();i++)
                dp.add(null);
            LinkedList<String> empty = new LinkedList<>();
            empty.add("");
            dp.set(0,empty);
            
            wordSizes = new TreeSet<Integer>();
            for(String word : wordDict)
                wordSizes.add(word.length());
            
            this.s = s;
            this.wordDict = wordDict;
            return getListEndedAt(s.length());
        }
        private LinkedList<String> getListEndedAt(int i){
            LinkedList rtn = dp.get(i);
            if(rtn!=null)
                return rtn;
            rtn = new LinkedList<String>();
            for(int wordSize : wordSizes){
                if(i-wordSize<0)
                    break;    //TreeSet is a sorted set.
                String substr = s.substring(i-wordSize,i);
                if(!wordDict.contains(substr))
                    continue;
                for(String prev : getListEndedAt(i-wordSize)){
                    if(i==wordSize)
                        rtn.add(substr);
                    else
                        rtn.add(prev+" "+substr);
                }
            }
            dp.set(i,rtn);
            return rtn;
        }
    }
    

Log in to reply
 

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