Java DFS + DP clean solution


  • 6
    Y

    The basic backtracking idea is straightforward, find a possible break point and then recursively call the suffix of the original string. The trick is that we use a map to keep the previous result which will terminate the recursion early to make sure we don't get TLE.

    public class Solution {
        public List<String> wordBreak(String s, Set<String> dict) {
            return dfs(s, dict, new HashMap<>());
        }
    
        public List<String> dfs(String s, Set<String> dict, Map<String, List<String>> memo){
            if(memo.containsKey(s)) {
                return memo.get(s);
            }
            List<String> res = new ArrayList<>();
            if(s == null || s.length() == 0) {
                return res;
            }
            int n = s.length();
            
            for(String w : dict) {
                if(!s.startsWith(w)) {
                    continue;
                }
                int end = w.length();
                if(end == n) {
                    res.add(w);
                } else {
                    List<String> sublist = dfs(s.substring(end), dict, memo);
                    for(String item : sublist) {
                        item = w + " " + item;
                        res.add(item);
                    }
                }
            }
            
            memo.put(s, res);
            return res;
        }
    }

  • 0
    Z

    This is a worked solution from all the other top post,
    Using memo to reduce the time of doing DFS is nice

    Nice and easy understand solution


Log in to reply
 

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