Why does my code get Time Limit Exceeded


  • 0
    L

    my code is as follow

    public class Solution {
    	public boolean wordBreak(String s, Set<String> dict) {
            if(s == null || dict.size() == 0) return false;
            boolean result = false;
            for(int i = 1; i <= s.length(); i++){
                if(dict.contains(s.substring(0, i))){
                    result = wordBreak(s.substring(i), dict);
                    if(result == true) break;
                }
            }
            return result;
        }
    }
    

    the last executed input is "acaaaaabbbdbcccdcdaadcdccacbcccabbbbcdaaaaaadb"
    . the dict contains "a" "b" "c“ and "d", so my answer will check the string from 0 to end once. why does it always get Time Limit Exceeded. I use recursive in my code, is it the reason?


  • 0
    E

    Yes, that is the reason. You can use a HashMap to store the results of each substring, and instead of recalculating the result each time (and invoking unnecessary recursion), you can just retrieve your pre-computed result. This is called memoization, and is an important aspect of DP (dynamic programming)

    (You may think your code is O(n), but it's not, due to the recursive nature of the function)


Log in to reply
 

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