Memoized solution


  • 0
        public List<String> wordBreak(String s, Set<String> wordDict) {
            Map<String, ArrayList<String>> map = new HashMap<>();
            return helper(s, wordDict, map);
        }
        
        public ArrayList<String> helper(String s, Set<String> wordDict, Map<String, ArrayList<String>> memo) {
            if (memo.containsKey(s)) {
                return memo.get(s);
            }
            ArrayList<String> result = new ArrayList<String>();
            if (s.isEmpty()) {
                result.add("");
                return result;
            }
            for (int i = 0; i <= s.length(); i++) {
                String firstHalf = s.substring(0, i);
                if (wordDict.contains(firstHalf)) {
                    String secondHalf = s.substring(i);
                    ArrayList<String> temp = helper(secondHalf, wordDict, memo);
                    for (String scentence : temp) {
                        if (scentence.isEmpty()) {
                            result.add(firstHalf + scentence);
                        } else {
                            result.add(firstHalf + " " + scentence);
                        }
                    }
                }
            }
            memo.put(s, result);
            return result;
        }
    

    Since we get lots of repeat work. Just use a hashmap to store our result so we don't have to compute over and over again.


Log in to reply
 

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