DP in Java easy to understand


  • 0
    A
      public List<String> wordBreak(String s, Set<String> wordDict) {
            HashMap<String, List<String>> map = new HashMap<String, List<String>>();
            return wordBreak(s, wordDict, map);
        }
    
        public List<String> wordBreak(String s, Set<String> wordDict,HashMap<String, List<String>> partialSolutions) {
            if (partialSolutions.containsKey(s))
                return partialSolutions.get(s);
            List<String> solutionForThisWord = new ArrayList<String>();
            if (s.length() < 1) {
                solutionForThisWord.add("");
                return solutionForThisWord;
            }
            for (String eachCandidateWord : wordDict) {
                if (s.startsWith(eachCandidateWord)) {
                    List<String> nextSolutions = wordBreak(s.replaceFirst(eachCandidateWord, ""), wordDict, partialSolutions);
                    for (String eachNextSolution : nextSolutions) {
                        if (eachNextSolution.length() > 0)
                            solutionForThisWord.add(eachCandidateWord + " " + eachNextSolution);
                        else
                            solutionForThisWord.add(eachCandidateWord);
                    }
                }
            }
            partialSolutions.put(s, solutionForThisWord);
            return solutionForThisWord;
        }

  • 0
    C

    modify
    s.replaceFirst(eachCandidateWord, "")
    to
    s.subString(eachCandidateWord.length())

    will improve the performance a bit.


Log in to reply
 

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