Why does my dp solution has the TLE problem? Anyone can help?


  • 0
    R

    This is my dp solution with recursion, I cannot figure out why it fails with long input, can anyone help?

        public boolean wordBreak(String s, Set<String> wordDict) {
            if (s == null || s.length() == 0) return false;
            Set<String> look = new HashSet<>();
            return wordBreak(s, wordDict, look);
        }
    
        private boolean wordBreak(String s, Set<String> wordDict, Set<String> look) {
            if (look.contains(s) || s == null || s.length() == 0) return true;
            int n = s.length();
            int i = 1;
            for (; i <= n; i++) {
                if (wordDict.contains(s.substring(0, i)) && wordBreak(s.substring(i), wordDict, look))
                    break;
            }
            if (i <= n) {
                look.add(s);
                return true;
            }
            else return false;
        }
    

    TLE test case:

    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
    ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
    

  • 0
    E

    Your code works fine when there is a matching solution. However, if the input string doesn't have a solution, your run time can become exponential. I think this is more of a "backtracking" solution than a DP one. You don't have any real memoization that reduces the amount you're checking.

    I tested with similar input with your code and with 15 total chars (aaaaaaaaaaaaaab) and it ran the wordDict.contains check over 30k times (in this case 2^15). This is due to the nature of the input string and the dictionary, but you can imagine how much the input you're getting the TLE on is branching.


Log in to reply
 

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