Time Limit Exceeded of Java DP


  • 1
    L

    Hi I totally have no idea how to modify my code for passing the aaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaa test, is someone could help me with it? Appreciate it!!!!!

    public List<String> wordBreak(String s, Set<String> wordDict) {
        Map<Integer,List<String>> validMap = new HashMap<Integer, List<String>>();
        int length = s.length();
        List<String> sentence = new ArrayList<>();
        sentence.add("");
        validMap.put(length,sentence);
    
        for(int i = s.length()-1; i>=0;i--){
            List<String> tempsentence = new ArrayList<>();
            for(int j = i+1;j<=s.length();j++){
                if(wordDict.contains(s.substring(i,j))){
                    for(String word : validMap.get(j)){
                        tempsentence.add(s.substring(i,j)+(j==length?"":" ")+word);
                    }
                }
            }
            validMap.put(i,tempsentence);
        }
        return validMap.get(0);
    }

Log in to reply
 

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