Java Top Down DP Solution beat 98.56%


  • 2
    A

    public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {

        List<String> res = new ArrayList<>();
        if(s == null || s.length() == 0) return res;
        int maxLen = 0;
        Set<String> set = new HashSet<>();
        for(String word: wordDict) {
            set.add(word);
            maxLen = Math.max(maxLen, word.length());
        }
        Map<Integer, List<String>> map = new HashMap<>();
        return search(s, 0, set, maxLen, map);
        
    }
    
    public List<String> search(String s, int start, Set<String> wordDict, int maxLen, Map<Integer, List<String>> map) {
        
        if(map.containsKey(start)) {
            return map.get(start);
        }
        
        List<String> res = new ArrayList<>();
        
        if(start == s.length()) {
            res.add("");
            return res;
        }
        
        for(int len = 1;len <= Math.min(s.length() - start, maxLen);len++) {
            String cur = s.substring(start, start + len);
            if(wordDict.contains(cur)) {
                List<String> next = search(s, start + len, wordDict, maxLen, map);
                
                for(int i = 0;i < next.size();i++) {
                    String temp = next.get(i);
                    res.add((cur + " " + temp).trim());
                }
            }
        }
        map.put(start, res);
        return res;
    }
    

    }


Log in to reply
 

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