Who can tell me why it will cause Time Limit Exceeded


  • 0

    ///
    public class Solution {
    private int getMaxLen(Set<String> wordDict){
    int max = 0;
    for(String ele : wordDict){
    max = Math.max(max, ele.length());
    }
    return max;
    }
    private boolean[][] isInDict(String s, Set<String> wordDict){
    int len = s.length();
    boolean[][] table = new boolean[len][len];
    int maxLen = getMaxLen(wordDict);
    for(int i = 0; i < len; i++){
    for(int j = i; j < len && (j + 1 - i <= maxLen); j++){
    if(wordDict.contains(s.substring(i, j+1))){
    table[i][j] = true;
    }
    }
    }
    return table;
    }

    public List<String> wordBreak(String s, Set<String> wordDict) {
        
        if(s == null || wordDict == null){
            return new ArrayList<String>();
        }
        int len = s.length();
        boolean[][] table = isInDict(s, wordDict);
        List<List<String>> res  = new ArrayList<List<String>>(); 
        List<String> emptyString = new ArrayList<String>();
        emptyString.add("");
        res.add(emptyString);
        for(int i = 1; i < len + 1; i++){
            List<String> curr = new ArrayList<String>();
            for(int j = 0; j < i; j++){
                if(table[j][i - 1]){
                    List<String> pre = res.get(j);
                    String subStr = s.substring(j, i);
                    for(String ele : pre){
                        String tempStr = new String(ele);
                        if(tempStr.equals("")){
                            tempStr += subStr;
                        }
                        else{
                            tempStr += " " + subStr;
                        }
                        curr.add(tempStr);
                    }
                }
            }
            res.add(curr);
        }
        return res.get(len);
    }
    

    }


Log in to reply
 

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