My Java Solution (DFS Recursion + HashMap)


  • 0
    C

    The result is based on building from the wordBreaks from substrings.

    public class Solution {
        HashMap<String, List<String>> map = new HashMap<>();
        public List<String> wordBreak(String s, List<String> wordDict) {
            if (map.containsKey(s)) return map.get(s);
            ArrayList<String> res = new ArrayList<>();
            res.add("");
            if (s.isEmpty()) return res;
            res = new ArrayList<>();
            for (int i = 0; i < wordDict.size(); i++) {
                    String match = wordDict.get(i);
                    if (s.indexOf(match) == 0) {
                        //Found a match, we start searching for the result of the remaining sub-string
                        List<String> subres = wordBreak(s.substring(match.length()), wordDict);
                        ArrayList<String> subres = new ArrayList<>();
                        for (int j = 0; j < subres.size(); j++) {
                            if (subres.get(j).isEmpty()) {
                                subres.add(match);
                            } else {
                                subres.add(match + " " + subres.get(j));
                            }
                        }
                        // Add all sub results to the result
                        res.addAll(subres);
                    }
            }
            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.