JAVA solution with memorization


  • 3
    F
    private Map<String, List<String>> map = new HashMap<>();
    
        public List<String> wordBreak(String s, Set<String> wordDict) {
            if (map.containsKey(s)) {
                return map.get(s);
            }
            List<String> list = new ArrayList<>();
            if (wordDict.contains(s)) {
                list.add(s);
            }
            for (int i = 1; i < s.length(); i++) {
                String word = s.substring(i);
                if (wordDict.contains(word)) {
                    List<String> prior = wordBreak(s.substring(0, i), wordDict);
                    for (String s1 : prior) {
                        list.add(s1 + " " + word);
                    }
                }
            }
            map.put(s, list);
            return list;
        }
    

Log in to reply
 

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