[HELP] Why is my non-recursive DP solution getting TLE?


  • 1
    J

    My easy-to-understand DP non-recursive solution was getting TLE on this test case:
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

     public List<String> wordBreak(String s, Set<String> wordDict) {
        int len = s.length();
        int maxLen = getMaxWordLen(wordDict);
        HashMap<Integer, List<String>> sentences = new HashMap<Integer, List<String>>(); //put(i, list) stores the solution to s.substring(0,i)
        for (int i = 1; i <= len; i++) {
            String sub = s.substring(0,i);
            List<String> al = new ArrayList<String>();
            if (wordDict.contains(sub)) {
                al.add(sub);
            }
            for (int j = Math.max(1, (i-maxLen)); j < i ; j++) {
            	String word = s.substring(j,i);
                if (sentences.containsKey(j) && wordDict.contains(word)) {
                    for (String sentence : sentences.get(j)) {
                        al.add(sentence + " " + word);
                    }
                }
            }
            if (!al.isEmpty()) {
                sentences.put(i, al);
            }
        }
        return sentences.containsKey(len)?sentences.get(len):new ArrayList<String>();
    }
    

    The time complexity of my solution is O(mn) where m and n are the length of s and the maximal length of the words in wordDict respectively. The time complexity seems to be the same as some of the accepted recursive DP solutions on the forum but why is my non-recursive solution getting TLE?


  • 2
    L

    same problem

    using backtracking.

    Do not generate partial solutions during DP.

    finish DP, then use backtracking to generate solutions.


  • 0
    L

    Thanks for the information. I have exactly the same issue with C++ implementation.


Log in to reply
 

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