Memorized DFS but iterate over word instead of dictionary

  • 1

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

    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) {
                return map.get(s);
            List<String> res = new ArrayList<>();
            if(s.length() == 0) {
                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 {
            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.