Memorized DFS but iterate over word instead of dictionary


  • 1

    Inspired by the nice idea of this high-voted post:

    https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs/43

    The idea of this post is very neat. It uses a HashMap to avoid TLE using DFS. In the post it iterates over the dictionary and it could be somehow inefficient. Since the dictionary volume can be quite large. So I changed a little bit to iterate over the given word. Hope this helps.

    public class Solution {
        public List<String> wordBreak(String s, List<String> wordDict) {
            return dfs(s, wordDict, new HashMap<String, List<String>>());
        }
        public List<String> dfs(String s, List<String> wordDict, HashMap<String, List<String>> map) {
            if(map.containsKey(s))
                return map.get(s);
            List<String> res = new ArrayList<>();
            if(s.length() == 0) {
                res.add("");
                return res;
            }
            for(int i = 0; i < s.length(); i++) {
                String head = s.substring(0, i+1);
                if(wordDict.contains(head)) {
                    List<String> list = dfs(s.substring(i+1), wordDict, map);
                    for(String sub : list) {
                        if(sub.length() != 0) {
                            res.add(head + " " + sub);
                        } else {
                            res.add(head);
                        }
                    }
                }
            }
            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.