Look at this concise Java solution


  • 0
    H
    public class Solution {
        
        Map<String, List<String>> cache = new HashMap<>();
        
        public List<String> wordBreak(String s, Set<String> wordDict) {
            if (cache.containsKey(s)) return cache.get(s);
            List<String> res = new ArrayList<String>();
            if (s.length() == 0) res.add("");
            
            for (int end = 1; end <= s.length(); end ++) {
                String word = s.substring(0, end);
                if (wordDict.contains(word)) {
                    List<String> next = wordBreak(s.substring(end), wordDict);
                    for (int n_i = 0; n_i < next.size(); n_i ++) {
                        String ele = word + " " + next.get(n_i);
                        res.add(ele.trim());
                    }
                }
            }
            
            cache.put(s, res);
            return res;
        }
    }
    

  • 0
    M

    What will be the complexity of this solution?


Log in to reply
 

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