Java DP solution


  • 0
    J

    key is to memorize intermediate result, or you might get out of time.

    There's choice to loop on words in dictionary or DFS on the input string. If dictionary is small, it's ok to loop on dictionary. general cases are big dictionary. so most time better DFS on input string.

        public List<String> wordBreak(String s, List<String> wordDict) {
            List<String> result = new ArrayList<>();
            if (s == null || s.isEmpty()) return result;
            Set<String> dict = new HashSet<>();
            dict.addAll(wordDict);
            HashMap<String, List<String>> map = new HashMap<>();
            return wordBreak(s, dict, map);
        }
        
        private List<String> wordBreak(String s, Set<String> dict, Map<String, List<String>> map) {
            if (s.isEmpty()) return new ArrayList<>();
            List<String> res = map.get(s);
            if (res != null) return res;
            res = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {
                String substr = s.substring(0, i + 1);
                if (dict.contains(substr)) {
                    if (i < s.length() - 1) {
                        List<String> sublist = wordBreak(s.substring(i + 1), dict, map);
                        for (String ss : sublist) {
                            res.add(substr + " " + ss);
                        }
                    } else {
                        res.add(substr);
                    }
                }
            }
            map.put(s, res);
            return res;
        }
    

Log in to reply
 

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